Andreas Krebs

Publication Activity (10 Years)

Years Active: 2003-2022
Publications (10 Years): 53

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

Theor. Comput. Sci.

MFCS

University of Tübingen, Germany (PHD)

Education History

University of Tübingen, Germany

PHD

Publications

Andreas Krebs, Howard Straubing
Regular languages defined by first-order formulas without quantifier alternation. CoRR (2022)
Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing
Two-variable logics with some betweenness relations: Expressiveness, satisfiability and membership. Log. Methods Comput. Sci. 16 (3) (2020)
Nikhil Balaji, Andreas Krebs, Nutan Limaye
Skew circuits of small width. Theor. Comput. Sci. 821 (2020)
Henning Fernau, Till Fluschnik, Danny Hermelin, Andreas Krebs, Hendrik Molter, Rolf Niedermeier
Diminishable parameterized problems and strict polynomial kernelization. Comput. 9 (1) (2020)
Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing
Two-variable logics with some betweenness relations: Expressiveness, satisfiability and membership. CoRR (2019)
Michael Hahn, Andreas Krebs, Howard Straubing
Wreath Products of Distributive Forest Algebras. CoRR (2019)
Silke Czarnetzki, Andreas Krebs
A topological approach to non-uniform complexity. Inf. Comput. 269 (2019)
Eric Allender, Andreas Krebs, Pierre McKenzie
Better Complexity Bounds for Cost Register Automata. Theory Comput. Syst. 63 (3) (2019)
Andreas Krebs, Arne Meier, Martin Mundhenk
The model checking fingerprints of CTL operators. Acta Informatica 56 (6) (2019)
Célia Borlido, Mai Gehrke, Andreas Krebs, Howard Straubing
Difference hierarchies and duality with an application to formal languages. CoRR (2018)
Silke Czarnetzki, Andreas Krebs, Klaus-Jörn Lange
Visibly Pushdown Languages and Free Profinite Algebras. CoRR (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)
Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
The Algebraic Theory of Parikh Automata. Theory Comput. Syst. 62 (5) (2018)
Michael Hahn, Andreas Krebs, Howard Straubing
Wreath Products of Distributive Forest Algebras. LICS (2018)
Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing
An Algebraic Decision Procedure for Two-Variable Logic with a Between Relation. CSL (2018)
Henning Fernau, Till Fluschnik, Danny Hermelin, Andreas Krebs, Hendrik Molter, Rolf Niedermeier
Diminishable Parameterized Problems and Strict Polynomial Kernelization. CiE (2018)
Andreas Krebs, Arne Meier, Jonni Virtema, Martin Zimmermann
Team Semantics for the Specification and Verification of Hyperproperties. MFCS (2018)
Célia Borlido, Silke Czarnetzki, Mai Gehrke, Andreas Krebs
Stone Duality and the Substitution Principle. CSL (2017)
Andreas Krebs, Nutan Limaye, Michael Ludwig
A Unified Method for Placing Problems in Polylogarithmic Depth. FSTTCS (2017)
Andreas Krebs, Nutan Limaye, Michael Ludwig
A Unified Method for Placing Problems in Polylogarithmic Depth. Electron. Colloquium Comput. Complex. 24 (2017)
Eric Allender, Andreas Krebs, Pierre McKenzie
Better Complexity Bounds for Cost Register Automata. MFCS (2017)
Eric Allender, Andreas Krebs, Pierre McKenzie
Better Complexity Bounds for Cost Register Machines. Electron. Colloquium Comput. Complex. 24 (2017)
Andreas Krebs, Howard Straubing
An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic. ACM Trans. Comput. Log. 18 (4) (2017)
Peter Chini, Jonathan Kolberg, Andreas Krebs, Roland Meyer, Prakash Saivasan
On the Complexity of Bounded Context Switching. ESA (2017)
Henning Fernau, Andreas Krebs
Problems on Finite Automata and the Exponential Time Hypothesis. Algorithms 10 (1) (2017)
Mai Gehrke, Andreas Krebs
Stone duality for languages and complexity. ACM SIGLOG News 4 (2) (2017)
Andreas Krebs, Arne Meier, Jonni Virtema, Martin Zimmermann
Team Semantics for the Specification and Verification of Hyperproperties. CoRR (2017)
Mai Gehrke, Andreas Krebs, Jean-Éric Pin
Ultrafilters on words for a fragment of logic. Theor. Comput. Sci. 610 (2016)
Olga Dorzweiler, Thomas Flamm, Andreas Krebs, Michael Ludwig
Positive and negative proofs for circuits and branching programs. Theor. Comput. Sci. 610 (2016)
Silke Czarnetzki, Andreas Krebs
Using Duality in Circuit Complexity. LATA (2016)
Michaël Cadilhac, Andreas Krebs, Klaus-Jörn Lange
A Language-Theoretical Approach to Descriptive Complexity. DLT (2016)
Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing
Two-variable Logic with a Between Relation. LICS (2016)
Andreas Krebs, Nutan Limaye, Michael Ludwig
Cost Register Automata for Nested Words. COCOON (2016)
Michael Blondin, Andreas Krebs, Pierre McKenzie
The complexity of intersecting finite automata having few final states. Comput. Complex. 25 (4) (2016)
Henning Fernau, Till Fluschnik, Danny Hermelin, Andreas Krebs, Hendrik Molter, Rolf Niedermeier
Diminishable Parameterized Problems and Strict Polynomial Kernelization. CoRR (2016)
Andreas Krebs, Meena Mahajan, Anil Shukla
Relating two width measures for resolution proofs. Electron. Colloquium Comput. Complex. 23 (2016)
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
Small Depth Proof Systems. ACM Trans. Comput. Theory 9 (1) (2016)
Henning Fernau, Andreas Krebs
Problems on Finite Automata and the Exponential Time Hypothesis. CIAA (2016)
Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing
Two-variable Logic with a Between Predicate. CoRR (2016)
Andreas Krebs, Arne Meier, Martin Mundhenk
The Model Checking Fingerprints of CTL Operators. TIME (2015)
Andreas Krebs, Oleg Verbitsky
Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth. LICS (2015)
Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig
and NL. DLT (2015)
Michael Hahn, Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig
. MFCS (2) (2015)
Nikhil Balaji, Andreas Krebs, Nutan Limaye
Skew Circuits of Small Width. COCOON (2015)
Christoph Berkholz, Andreas Krebs, Oleg Verbitsky
Bounds for the Quantifier Depth in Finite-Variable Logics: Alternation Hierarchy. ACM Trans. Comput. Log. 16 (3) (2015)
Michaël Cadilhac, Andreas Krebs, Nutan Limaye
Value Automata with Filters. CoRR (2015)
Silke Czarnetzki, Andreas Krebs
Using Duality in Circuit Complexity. CoRR (2015)
Andreas Krebs, Arne Meier, Jonni Virtema
Parallel Computational Tree Logic. CoRR (2015)
Andreas Krebs, Arne Meier, Martin Mundhenk
The model checking fingerprints of CTL operators. CoRR (2015)
Michaël Cadilhac, Andreas Krebs, Michael Ludwig, Charles Paperman
A Circuit Complexity Approach to Transductions. MFCS (1) (2015)
Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig
Visibly Counter Languages and Constant Depth Circuits. STACS (2015)
Andreas Krebs, Howard Straubing
EF+EX Forest Algebras. CAI (2015)
Andreas Krebs, Arne Meier, Jonni Virtema
A Team Based Variant of CTL. TIME (2015)
Andreas Krebs, Oleg Verbitsky
Universal covers, color refinement, and two-variable logic with counting quantifiers: Lower bounds for the depth. CoRR (2014)
Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig
Visibly Counter Languages and Constant Depth Circuits. Electron. Colloquium Comput. Complex. 21 (2014)
Christoph Hering, Andreas Krebs, Thomas Edgar
Naive configurations. Des. Codes Cryptogr. 72 (3) (2014)
Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
Extremely uniform branching programs. NCMA (2014)
Mai Gehrke, Andreas Krebs, Jean-Éric Pin
From Ultrafilters on Words to the Expressive Power of a Fragment of Logic. DCFS (2014)
Olga Dorzweiler, Thomas Flamm, Andreas Krebs, Michael Ludwig
Positive and Negative Proofs for Circuits and Branching Programs. DCFS (2014)
Matthias Maischak, Andreas Krebs, Ernst P. Stephan
Quasi-optimal degree distribution for a quadratic programming problem arising from the p-version finite element method for a one-dimensional obstacle problem. Discret. Appl. Math. 164 (2014)
Andreas Krebs, Howard Straubing
EF+EX Forest Algebras. CoRR (2014)
Nikhil Balaji, Andreas Krebs, Nutan Limaye
Skew Circuits of Small Width. Electron. Colloquium Comput. Complex. 21 (2014)
Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
The Algebraic Theory of Parikh Automata. CAI (2013)
Andreas Krebs, Nutan Limaye
DLOGTIME Proof Systems. FSTTCS (2013)
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
Small Depth Proof Systems. Electron. Colloquium Comput. Complex. 20 (2013)
Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
The Algebraic Theory of Parikh Automata. Electron. Colloquium Comput. Complex. 20 (2013)
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
Small Depth Proof Systems. CoRR (2013)
Christoph Berkholz, Andreas Krebs, Oleg Verbitsky
Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy. CSL (2013)
Christoph Behle, Andreas Krebs, Mark Mercer
Linear circuits, two-variable logic and weakly blocked monoids. Theor. Comput. Sci. 501 (2013)
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
Small Depth Proof Systems. MFCS (2013)
Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer
Verifying proofs in constant depth. ACM Trans. Comput. Theory 5 (1) (2013)
Michael Blondin, Andreas Krebs, Pierre McKenzie
The Complexity of Intersecting Finite Automata Having Few Final States. Electron. Colloquium Comput. Complex. 19 (2012)
Andreas Krebs, Nutan Limaye, Srikanth Srinivasan
Streaming algorithms for recognizing nearly well-parenthesized expressions CoRR (2012)
Andreas Krebs, Howard Straubing
An effective characterization of the alternation hierarchy in two-variable logic CoRR (2012)
Andreas Krebs, Nutan Limaye
DLOGTIME-Proof Systems. Electron. Colloquium Comput. Complex. 19 (2012)
Andreas Krebs, Nutan Limaye, Meena Mahajan
Counting Paths in VPA Is Complete for #NC 1. Algorithmica 64 (2) (2012)
Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie
The Lower Reaches of Circuit Uniformity. MFCS (2012)
Andreas Krebs, A. V. Sreejith
Non-definability of languages by generalized first-order formulas over (N,+) CoRR (2012)
Andreas Krebs, A. V. Sreejith
Non-definability of Languages by Generalized First-order Formulas over (N, +). LICS (2012)
Andreas Krebs, Howard Straubing
An effective characterization of the alternation hierarchy in two-variable logic. FSTTCS (2012)
Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer
Verifying Proofs in Constant Depth. Electron. Colloquium Comput. Complex. 19 (2012)
Andreas Krebs, Klaus-Jörn Lange
Dense Completeness. Developments in Language Theory (2012)
Andreas Krebs, Nutan Limaye, Srikanth Srinivasan
Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions. MFCS (2011)
Christoph Behle, Andreas Krebs
Regular Languages in MAJ[>] with three variables. Electron. Colloquium Comput. Complex. 18 (2011)
Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie
Low uniform versions of NC1. Electron. Colloquium Comput. Complex. 18 (2011)
Andreas Krebs, Johan Wiklund, Michael Felsberg
Optimization of Quadrature Filters Based on the Numerical Integration of Improper Integrals. DAGM-Symposium (2011)
Christoph Behle, Andreas Krebs, Stephanie Reifferscheid
Typed Monoids - An Eilenberg-Like Theorem for Non Regular Languages. CAI (2011)
Christoph Behle, Andreas Krebs, Stephanie Reifferscheid
Typed Monoids - An Eilenberg-like Theorem for non regular Languages. Electron. Colloquium Comput. Complex. 18 (2011)
Andreas Krebs, Nutan Limaye, Meena Mahajan
. Electron. Colloquium Comput. Complex. 17 (2010)
Andreas Krebs, Nutan Limaye, Meena Mahajan
. COCOON (2010)
Matthias Maischak, Andreas Krebs, Ernst P. Stephan
A quadratic programming problem arising from the p-version for obstacle problems. Electron. Notes Discret. Math. 36 (2010)
Christoph Behle, Andreas Krebs, Stephanie Reifferscheid
Regular Languages Definable by Majority Quantifiers with Two Variables. Developments in Language Theory (2009)
Christoph Behle, Andreas Krebs, Stephanie Reifferscheid
An Approach to characterize the Regular Languages in TC0 with Linear Wires. Electron. Colloquium Comput. Complex. 16 (2009)
Christoph Behle, Andreas Krebs, Stephanie Reifferscheid
Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG]. LATA (2009)
Christoph Hering, Andreas Krebs
A partial plane of order 6 constructed from the icosahedron. Des. Codes Cryptogr. 44 (1-3) (2007)
Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson, Denis Thérien
Languages with Bounded Multiparty Communication Complexity. STACS (2007)
Andreas Krebs, Ernst P. Stephan
-version finite element method for nonlinear elliptic variational inequalities in 2D. Numerische Mathematik 105 (3) (2007)
Christoph Behle, Andreas Krebs, Mark Mercer
Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids. MFCS (2007)
Andreas Krebs, Klaus-Jörn Lange, Stephanie Reifferscheid
in Terms of Infinite Groups. Theory Comput. Syst. 40 (4) (2007)
Arkadev Chattopadhyay, Michal Koucký, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien
Languages with Bounded Multiparty Communication Complexity. Electron. Colloquium Comput. Complex. 13 (117) (2006)

Andreas Krebs.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Andreas Krebs