Dr. Andreas Krebs

E-Mail: krebs(at)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

Lehre

Forschungsinteressen

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

Publications / Talks

2016

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


nach oben

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)

 


nach oben

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)

nach oben

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


nach oben

2011


nach oben

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


nach oben