Dr. Andreas Krebs

Zweimal im Jahr organisiere ich einen Workshop, der mittlerweile bereits über die Grenzen der Theorie-Gruppe in Tübingen heraus gewachsen ist.

Im Wintersemester halte ich gemeinsam mit Silke Czarnetzki die Vorlesung Spezielle Kapitel der theoretischen Informatik: Duality in Computer Science.

• Parallele Algorithmen/Schaltkreiskomplexität
• Logik/Descriptive Complexity
• Algebraische und Topologische Methoden
• Modelchecking/Verifikation
• Endliche Geometrien/Kodierungstheorie

• 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

• 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)

• 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
  

• 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)

nach oben

• 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)

nach oben

• 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)

nach oben

• 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

nach oben

nach oben

• 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

nach oben