Dr. Andreas Krebs

EMail: This e-mail address is being protected from spambots. You need JavaScript enabled to view it.

Raum:B 115

Telefon:07071 / 29 77476

Adresse:

Universität Tübingen
Wilhelm-Schickard-Institut für Informatik
Arbeitsbereich Theoretische Informatik/Formale Sprachen
Sand 13
D-72076 Tübingen

Sprechzeiten nach Vereinbarung

Lehre

Auf vielfachen Studentenwunsch findet die Vorlesung Schaltkreiskomplexität am Donnerstag um 18Uhr statt!

Forschungsinteressen

• Formale Sprachen
• Logik/Descriptive Komplexity
• Schaltkreiskomplexität
• Gruppen und Monoide
• Endliche Geometrie
• Modelchecking/Hardwareverifikation

Publikationen/Talks

• Andreas Krebs, Klaus-Jörn Lange:
  Dense Completeness.
  DLT 2012 (accepted), August 2012
  
• Andreas Krebs, A V Sreejith:
  Non-definability of languages by generalized first-order formulas over (N,+).
  LICS 2012 (accepted), June 2012  
• Christoph Behle, Andreas Krebs:
  Regular Languages in MAJ[] with three variables.
  ECCC 2011(173), December 2011  
• Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie:
  Low uniform versions of NC1.
  ECCC 2011(95), June 2011  
• Andreas Krebs, Nutan Limaye,  Srikanth Srinivasan:
  Streaming algorithms for recognizing nearly well-parenthesized expressions.
  MFCS 2011. 412-423.
• Christoph Behle, Andreas Krebs, Stephanie Reifferscheid:
  Typed Monoids -- An Eilenberg-like Theorem for non regular Languages.
  ECCC 2011(35), Mar 2011 
• Christoph Behle, Andreas Krebs, Stephanie Reifferscheid:
  Typed Monoids - An Eilenberg-like Theorem for non regular Languages.
  CAI 2011. 97-114.
• Andreas Krebs, Nutan Limaye, Meena Mahajan:
  Counting paths in VPA is complete for #NC^1.
  ECCC 2010(103), June 2010
• Christoph Hering, Andreas Krebs:
  Orthomorphisms and Loops.
  Talk at the Groups and Topological Groups conference 2010.
• Andreas Krebs, Nutan Limaye, Meena Mahajan:
  Counting paths in VPA is complete for #NC^1.
  COONON 2010
• Christoph Behle, Andreas Krebs, Stephanie Reifferscheid:
  An Approach to characterize the Regular Languages in TC0 with Linear Wires.
  ECCC 2009(85), Sep 2009
• Christoph Hering, Andreas Krebs:
  Latin Squares, Homologies and Euler's Conjecture.
  Note di Matematica 29 (2009), suppl. n. 1, 115-120
• Christoph Behle, Andreas Krebs, Stephanie Reifferscheid:
  Regular Languages definable by Majority Quantifiers with two Variable.
  DLT 2009: p. 91-102, July 2009
• Christoph Behle, Andreas Krebs, Stephanie Reifferscheid:
  Non-Solvable Groups are not in FO+MOD+MÂJ₂[REG].
  LATA 2009: p. 129-140, April 2009
• Andreas Krebs:
  Typed Semigroups, Majority Logic, and Threshold Circuits.
  Dissertation Informatik, 2008
• Christoph Behle, Andreas Krebs, Mark Mercer:
  Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids.
  MFCS 2007: p.147-158
• Christoph Hering, Andreas Krebs:
  A partial plane of order 6 constructed from the icosahedron.
  Designs, Codes and Cryptography 44:1-3 September 2007.
• Andreas Krebs, Klaus-Jorn Lange, Stephanie Reifferscheid:
  Characterizing TC0 in Terms of Infinite Groups.
  Theory of Computing Systems 40:4, p. 303-325, July 2007.
• Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson, Denis Thérien:
  Languages with Bounded Multiparty Communication Complexity.
  STACS 2007: 500-511
• Andreas Krebs:
  Projektive Ebenen und Inzidenzmatrizen.
  Diplomarbeit Mathematik, 2005
• Andreas Krebs, Klaus-Jörn Lange, Stephanie Reifferscheid:
  Characterizing TC0 in Terms of Infinite Groups.
  STACS 2005: 496-507
• Lew Gordeev, Andreas Krebs:
  Elementary-algebraic interpretation of P vs NP.
  Talk at Second St.Petersburg Days of Logic and Computability 2003
• Andreas Krebs, Jürgen Ruf:
  Optimized Temporal Logic Compilation.
  J. UCS 9(2): 120-137 (2003)
• Andreas Krebs:
  Continous Grid Functions - a contribution to fuzzy logic.
  Diplomarbeit Informatik, 2002
• Andreas Krebs:
  A universal 5 state turing machine.
  Proof, Computation, Complexity International workshop: April 8th and 9th, 2002