Dr. Andreas Krebs

Adresse:

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

Sprechstunde: nach Vereinbarung

Forschungsinteressen

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

Publications / Talks

2016

• Michaël Cadilhac, Andreas Krebs, Klaus-Jörn Lange:
  A language-theoretical approach to descriptive complexity
  DLT 2016 (accepted)
• Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah:
  Small depth proof systems.
  ACM Transactions on Computation Theory (accepted)
• Andreas Krebs, Nutan Limaye, Michael Ludwig:
  Cost Register Automata for Nested Words
  COCOON 2016 (accepted)
• Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing:
  Two-variable Logic with a Between Relation.
  LICS 2016 (accepted)
• Henning Fernau, Andreas Krebs:
  P roblems on Finite Automata and the Exponential Time Hypothesis
  CIAA 2016 (accepted)
• Olga Dorzweiler, Thomas Flamm, Andreas Krebs, Michael Ludwig:
  Positive and negative proofs for circuits and branching programs.
  Theoretical Computer Science 610: 24-36
• Mai Gehrke, Andreas Krebs, Jean-Éric Pin:
  Ultrafilters on words for a fragment of logic.
  Theoretical Computer Science 610: 37-58
• Silke Czarnetzki, Andreas Krebs:
  Using Duality in Circuit Complexity.
  LATA 2016: 283-294
• Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing:
  Two-variable Logic with a Between Predicate.
  arXiv:1603.05625

2015

• Christoph Berkholz, Andreas Krebs, Oleg Verbitsky:
  Bounds for the Quantifier Depth in Finite-Variable Logics: Alternation
  Hierarchy.
  ACM Transactions on Computational Logic 16(3): 21
• Andreas Krebs, Arne Meier, Martin Mundhenk:
  The model checking fingerprints of CTL operators
  TIME 2015: 101-110
• Andreas Krebs, Arne Meier, Jonni Virtema:
  A Team Based Variant of CTL
  TIME 2015: 140-149
• Andreas Krebs and Howard Straubing:
  EF+EX Forest Algebras
  CAI 2015: 128-139
• Michaël Cadilhac, Andreas Krebs, Michael Ludwig and Charles Paperman:
  A Circuit Complexity Approach to Transductions
  MFCS 2015: 141-153
• Michael Hahn, Klaus-Joern Lange, Andreas Krebs and Michael Ludwig:
  Visibly Counter Languages and the Structure of NC1
  MFCS 2015: 384-394
• Michael Ludwig, Andreas Krebs and Klaus-Jörn Lange:
  On Distinguishing NC1 and NL.
  DLT 2015: 340-351
• Nikhil Balaji, Andreas Krebs, Nutan Limaye:
  Skew Circuits of Small Width.
  COCOON 2015: 199-210
• Andreas Krebs, Oleg Verbitsky:
  Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth.
  LICS 2015: 689-700
• Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig:
  Visibly Counter Languages and Constant Depth Circuits.
  STACS 2015: 594-607
• Andreas Krebs, Arne Meier, Martin Mundhenk:
  The model checking fingerprints of CTL operators.
  CoRR 1504.04708v1 (2015)

2014

• Christoph Hering, Andreas Krebs, Thomas Edgar:
  Naive configurations.
  Des. Codes Cryptography 72(3): 719-731 (2014)
• Mai Gehrke, Andreas Krebs, Jean-Éric Pin:
  From Ultrafilters on Words to the Expressive Power of a Fragment of Logic.
  DCFS 2014: 138-149
• Olga Dorzweiler, Thomas Flamm, Andreas Krebs, Michael Ludwig:
  Positive and Negative Proofs for Circuits and Branching Programs.
  DCFS 2014: 270-281
• Michaël Cadilhac, Andreas Krebs, Pierre McKenzie:
  Extremely uniform branching programs.
  NCMA 2014: 73-83
• Andreas Krebs, Oleg Verbitsky:
  Universal covers, color refinement, and two-variable logic with counting quantifiers: Lower bounds for the depth.
  CoRR abs /1407.3175 (2014)
• Andreas Krebs, Howard Straubing:
  EF+EX Forest Algebras.
  CoRR abs/1408.0809 (2014)
• Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig:
  Visibly Counter Languages and Constant Depth Circuits.
  Electronic Colloquium on Computational Complexity (ECCC) 21: 177 (2014)
• Nikhil Balaji, Andreas Krebs, Nutan Limaye:
  Skew Circuits of Small Width.
  Electronic Colloquium on Computational Complexity (ECCC) 21: 183 (2014)

2013

• Christoph Behle, Andreas Krebs, Mark Mercer:
  Linear circuits, two-variable logic and weakly blocked monoids.
  Theor. Comput. Sci. 501: 20-33 (2013)
• Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer:
  Verifying proofs in constant depth.
  TOCT 5(1): 2 (2013)
• Michaël Cadilhac, Andreas Krebs, Pierre McKenzie:
  The Algebraic Theory of Parikh Automata.
  CAI 2013: 60-73
• Christoph Berkholz, Andreas Krebs, Oleg Verbitsky:
  Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy.
  CSL 2013: 61-80
• Andreas Krebs, Nutan Limaye:
  DLOGTIME Proof Systems.
  FSTTCS 2013: 189-200
• Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah:
  Small Depth Proof Systems.
  MFCS 2013: 583-594
• Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah:
  Small Depth Proof Systems.
  CoRR abs/1307.4897 (2013)
• Michaël Cadilhac, Andreas Krebs, Pierre McKenzie:
  The Algebraic Theory of Parikh Automata.
  Electronic Colloquium on Computational Complexity (ECCC) 20: 40 (2013)
• Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah:
  Small Depth Proof Systems.
  Electronic Colloquium on Computational Complexity (ECCC) 20: 102 (2013)

2012

• Andreas Krebs, Nutan Limaye:
  DLOGTIME-Proof Systems.
  ECCC 2012(TR12-186), Dez 2012
• Andreas Krebs, Howard Straubing:
  An effective characterization of the alternation hierarchy in two-variable logic. FSTTCS (accepted), December 2012
• Christoph Hering, Andreas Krebs, Thomas Edgar:
  Lexicographic Configurations.
  arXiv:1211.1899, Nov 2012
• Michael Blondin, Andreas Krebs, Pierre McKenzie:
  The Complexity of Intersecting Finite Automata Having Few Final States.
  ECCC 2012(TR12-090), June 2012
• Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer:
  Verifying Proofs in Constant Depth.
  ECCC 2012(TR12-079), June 2012
• Andreas Krebs, Nutan Limaye, Meena Mahajan:
  Counting paths in VPA is complete for #NC^1.
  Algorithmica 64(2): 279-294 (2012)
• Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie:
  The lower reaches of circuit uniformity.
  MFCS 2012 (accepted), August 2012.
• Andreas Krebs, Howard Straubing:
  An effective characterization of the alternation hierarchy in two-variable logic. arXiv:1205.4802v1, Mai 2012
• Andreas Krebs, Klaus-Jörn Lange:
  Dense Completeness. DLT 2012: 178-189, August 2012
• Andreas Krebs, A V Sreejith:
  Non-definability of languages by generalized first-order formulas over (N,+). LICS 2012: 451-460, June 2012

2011

• Christoph Behle, Andreas Krebs:
  Regular Languages in MAJ[order] 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.

Previous Publications / Talks

• 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 (2 009), 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ÂJ2[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