Dr. Andreas Krebs
E-Mail: krebs @informatik.uni-tuebingen.de
Raum: B115
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
Sprechstunde: nach Vereinbarung
Zweimal im Jahr organisiere ich einen Workshop, der mittlerweile bereits über die Grenzen der Theorie-Gruppe in Tübingen heraus gewachsen ist.
Lehre
Im Wintersemester halte ich gemeinsam mit Silke Czarnetzki die Vorlesung Spezielle Kapitel der theoretischen Informatik: Duality in Computer Science.
Forschungsinteressen
- Parallele Algorithmen/Schaltkreiskomplexität
- Logik/Descriptive Complexity
- Algebraische und Topologische Methoden
- Modelchecking/Verifikation
- Endliche Geometrien/Kodierungstheorie
Publications / Talks
2018
- Andreas Krebs, Kamal Lodaya, Paritosh Pandya,Howard Straubing
An algebraic decision procedure for two-variable logic with a between relation
CSL 2018 (accepted) - Andreas Krebs, Arne Meier, Jonni Virtema, Martin Zimmermann
Team Semantics for the Specification and Verification of Hyperpropertiesinformation
MFCS 2018 (accepted) - Henning Fernau, Till Fluschnik, Danny Hermelin, Andreas Krebs, Hendrik Molter, Rolf Niedermeier
Diminishable Parameterized Problems and Strict Polynomial Kernelization
CiE 2018 (accepted) - Michael Hahn, Andreas Krebs, Howard Straubing
Wreath Products of Distributive Forest Algebras
LICS 2018: 512-520 - Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
The Algebraic Theory of Parikh Automata
Theory Comput. Syst. 62(5): 1241-1268 (2018) - Demen Güler, Andreas Krebs, Klaus-Jörn Lange, Petra Wolf
Deciding Regular Intersection Emptiness of Complete Problems for PSPACE and the Polynomial Hierarchy
LATA 2018: 156-168
2017
- Henning Fernau, Andreas Krebs
Problems on Finite Automata and the Exponential Time Hypothesis
Algorithms 10(1): 24 (2017) - Mai Gehrke, Andreas Krebs
Stone duality for languages and complexity
SIGLOG News 4(2): 29-53 (2017) - Andreas Krebs, Howard Straubing
An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic
ACM Trans. Comput. Log. 18(4): 30:1-30:22 (2017) - Célia Borlido, Silke Czarnetzki, Mai Gehrke, Andreas Krebs
Stone Duality and the Substitution Principle
CSL 2017: 13:1-13:20 - Peter Chini, Jonathan Kolberg, Andreas Krebs, Roland Meyer, Prakash Saivasan
On the Complexity of Bounded Context Switching
ESA 2017: 27:1-27:15 - Andreas Krebs, Nutan Limaye, Michael Ludwig
A Unified Method for Placing Problems in Polylogarithmic Depth
FSTTCS 2017: 36:36-36:15 - Eric Allender, Andreas Krebs, Pierre McKenzie
Better Complexity Bounds for Cost Register Automata
MFCS 2017: 24:1-24:14 - Andreas Krebs, Arne Meier, Jonni Virtema, Martin Zimmermann
Team Semantics for the Specification and Verification of Hyperproperties
CoRR abs/1709.08510 (2017) - Andreas Krebs, Nutan Limaye, Michael Ludwig
A Unified Method for Placing Problems in Polylogarithmic Depth
Electronic Colloquium on Computational Complexity (ECCC) 24: 19 (2017) - Eric Allender, Andreas Krebs, Pierre McKenzie
Better Complexity Bounds for Cost Register Machines
Electronic Colloquium on Computational Complexity (ECCC) 24: 72 (2017)
2016
- Andreas Krebs, Meena Mahajan, Anil Shukla
Relating two width measures for resolution proofs
Colloquium on Computational Complexity (ECCC) 23: 164 (2016) - Henning Fernau, Till Fluschnik, Danny Hermelin, Andreas Krebs, Hendrik Molter, Rolf Niedermeier
Diminishable Parameterized Problems and Strict Polynomial Kernelization
arxiv:1611.03739 - Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah:
Small Depth Proof Systems
Journal ACM Transactions on Computation Theory (TOCT), Volume 9(1) 2016 - Michael Blondin, Andreas Krebs, Pierre McKenzie:
The complexity of intersecting finite automata having few final states
computational complexity Volume 25(4), pp. 775-814 (2016) - Michaël Cadilhac, Andreas Krebs, Pierre McKenzie:
The algebraic theory of Parikh automata
Theory of Computing Systems (TOCS) (accepted). - 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:
Problems 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 (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Â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