Andreas Krebs - RankMe

108 papers A* 5A 4B 9C 11Misc 3Journal 62Unranked 13

Year	Rank	Type	Title / Venue / Authors
2026	—	`conf`	When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames. FoIKS Andreas Krebs, Arne Meier
2025	A*	`conf`	A Formal Framework for Understanding Length Generalization in Transformers. ICLR Xinting Huang, Andy Yang, Satwik Bhattamishra, Yash Raj Sarrof, Andreas Krebs, Hattie Zhou, Preetum Nakkiran, Michael Hahn
2025	J	`jnl`	When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames. CoRR Andreas Krebs, Arne Meier
2024	J	`jnl`	A Formal Framework for Understanding Length Generalization in Transformers. CoRR Xinting Huang, Andy Yang, Satwik Bhattamishra, Yash Raj Sarrof, Andreas Krebs, Hattie Zhou, Preetum Nakkiran, Michael Hahn
2024	J	`jnl`	Synchronous Team Semantics for Temporal Logics. CoRR Andreas Krebs, Arne Meier, Jonni Virtema, Martin Zimmermann
2022	J	`jnl`	Regular languages defined by first-order formulas without quantifier alternation. CoRR Andreas Krebs, Howard Straubing
2020	J	`jnl`	Diminishable parameterized problems and strict polynomial kernelization. Comput. Henning Fernau, Till Fluschnik, Danny Hermelin, Andreas Krebs, Hendrik Molter, Rolf Niedermeier
2020	J	`jnl`	Skew circuits of small width. Theor. Comput. Sci. Nikhil Balaji, Andreas Krebs, Nutan Limaye
2020	J	`jnl`	Two-variable logics with some betweenness relations: Expressiveness, satisfiability and membership. Log. Methods Comput. Sci. Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing
2019	J	`jnl`	A topological approach to non-uniform complexity. Inf. Comput. Silke Czarnetzki, Andreas Krebs
2019	J	`jnl`	Better Complexity Bounds for Cost Register Automata. Theory Comput. Syst. Eric Allender, Andreas Krebs, Pierre McKenzie
2019	J	`jnl`	The model checking fingerprints of CTL operators. Acta Informatica Andreas Krebs, Arne Meier, Martin Mundhenk
2019	J	`jnl`	Two-variable logics with some betweenness relations: Expressiveness, satisfiability and membership. CoRR Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing
2019	J	`jnl`	Wreath Products of Distributive Forest Algebras. CoRR Michael Hahn, Andreas Krebs, Howard Straubing
2018	B	`conf`	An Algebraic Decision Procedure for Two-Variable Logic with a Between Relation. CSL Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing
2018	C	`conf`	Deciding Regular Intersection Emptiness of Complete Problems for PSPACE and the Polynomial Hierarchy. LATA Demen Güler, Andreas Krebs, Klaus-Jörn Lange, Petra Wolf
2018	J	`jnl`	Difference hierarchies and duality with an application to formal languages. CoRR Célia Borlido, Mai Gehrke, Andreas Krebs, Howard Straubing
2018	C	`conf`	Diminishable Parameterized Problems and Strict Polynomial Kernelization. CiE Henning Fernau, Till Fluschnik, Danny Hermelin, Andreas Krebs, Hendrik Molter, Rolf Niedermeier
2018	B	`conf`	Team Semantics for the Specification and Verification of Hyperproperties. MFCS Andreas Krebs, Arne Meier, Jonni Virtema, Martin Zimmermann
2018	J	`jnl`	The Algebraic Theory of Parikh Automata. Theory Comput. Syst. Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
2018	J	`jnl`	Visibly Pushdown Languages and Free Profinite Algebras. CoRR Silke Czarnetzki, Andreas Krebs, Klaus-Jörn Lange
2018	A*	`conf`	Wreath Products of Distributive Forest Algebras. LICS Michael Hahn, Andreas Krebs, Howard Straubing
2017	—	`conf`	A Unified Method for Placing Problems in Polylogarithmic Depth. FSTTCS Andreas Krebs, Nutan Limaye, Michael Ludwig
2017	J	`jnl`	A Unified Method for Placing Problems in Polylogarithmic Depth. Electron. Colloquium Comput. Complex. Andreas Krebs, Nutan Limaye, Michael Ludwig
2017	J	`jnl`	An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic. ACM Trans. Comput. Log. Andreas Krebs, Howard Straubing
2017	B	`conf`	Better Complexity Bounds for Cost Register Automata. MFCS Eric Allender, Andreas Krebs, Pierre McKenzie
2017	J	`jnl`	Better Complexity Bounds for Cost Register Machines. Electron. Colloquium Comput. Complex. Eric Allender, Andreas Krebs, Pierre McKenzie
2017	A	`conf`	On the Complexity of Bounded Context Switching. ESA Peter Chini, Jonathan Kolberg, Andreas Krebs, Roland Meyer, Prakash Saivasan
2017	J	`jnl`	Problems on Finite Automata and the Exponential Time Hypothesis. Algorithms Henning Fernau, Andreas Krebs
2017	B	`conf`	Stone Duality and the Substitution Principle. CSL Célia Borlido, Silke Czarnetzki, Mai Gehrke, Andreas Krebs
2017	J	`jnl`	Stone duality for languages and complexity. ACM SIGLOG News Mai Gehrke, Andreas Krebs
2017	J	`jnl`	Team Semantics for the Specification and Verification of Hyperproperties. CoRR Andreas Krebs, Arne Meier, Jonni Virtema, Martin Zimmermann
2016	C	`conf`	A Language-Theoretical Approach to Descriptive Complexity. DLT Michaël Cadilhac, Andreas Krebs, Klaus-Jörn Lange
2016	Misc	`conf`	Cost Register Automata for Nested Words. COCOON Andreas Krebs, Nutan Limaye, Michael Ludwig
2016	J	`jnl`	Diminishable Parameterized Problems and Strict Polynomial Kernelization. CoRR Henning Fernau, Till Fluschnik, Danny Hermelin, Andreas Krebs, Hendrik Molter, Rolf Niedermeier
2016	J	`jnl`	Positive and negative proofs for circuits and branching programs. Theor. Comput. Sci. Olga Dorzweiler, Thomas Flamm, Andreas Krebs, Michael Ludwig
2016	C	`conf`	Problems on Finite Automata and the Exponential Time Hypothesis. CIAA Henning Fernau, Andreas Krebs
2016	J	`jnl`	Relating two width measures for resolution proofs. Electron. Colloquium Comput. Complex. Andreas Krebs, Meena Mahajan, Anil Shukla
2016	J	`jnl`	Small Depth Proof Systems. ACM Trans. Comput. Theory Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
2016	J	`jnl`	The complexity of intersecting finite automata having few final states. Comput. Complex. Michael Blondin, Andreas Krebs, Pierre McKenzie
2016	J	`jnl`	Two-variable Logic with a Between Predicate. CoRR Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing
2016	A*	`conf`	Two-variable Logic with a Between Relation. LICS Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing
2016	J	`jnl`	Ultrafilters on words for a fragment of logic. Theor. Comput. Sci. Mai Gehrke, Andreas Krebs, Jean-Éric Pin
2016	C	`conf`	Using Duality in Circuit Complexity. LATA Silke Czarnetzki, Andreas Krebs
2015	—	`conf`	A Circuit Complexity Approach to Transductions. MFCS (1) Michaël Cadilhac, Andreas Krebs, Michael Ludwig, Charles Paperman
2015	C	`conf`	A Team Based Variant of CTL. TIME Andreas Krebs, Arne Meier, Jonni Virtema
2015	J	`jnl`	Bounds for the Quantifier Depth in Finite-Variable Logics: Alternation Hierarchy. ACM Trans. Comput. Log. Christoph Berkholz, Andreas Krebs, Oleg Verbitsky
2015	—	`conf`	EF+EX Forest Algebras. CAI Andreas Krebs, Howard Straubing
2015	C	`conf`	On Distinguishing NC DLT Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig
2015	J	`jnl`	Parallel Computational Tree Logic. CoRR Andreas Krebs, Arne Meier, Jonni Virtema
2015	Misc	`conf`	Skew Circuits of Small Width. COCOON Nikhil Balaji, Andreas Krebs, Nutan Limaye
2015	C	`conf`	The Model Checking Fingerprints of CTL Operators. TIME Andreas Krebs, Arne Meier, Martin Mundhenk
2015	J	`jnl`	The model checking fingerprints of CTL operators. CoRR Andreas Krebs, Arne Meier, Martin Mundhenk
2015	A*	`conf`	Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth. LICS Andreas Krebs, Oleg Verbitsky
2015	J	`jnl`	Using Duality in Circuit Complexity. CoRR Silke Czarnetzki, Andreas Krebs
2015	J	`jnl`	Value Automata with Filters. CoRR Michaël Cadilhac, Andreas Krebs, Nutan Limaye
2015	A	`conf`	Visibly Counter Languages and Constant Depth Circuits. STACS Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig
2015	—	`conf`	Visibly Counter Languages and the Structure of NC MFCS (2) Michael Hahn, Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig
2014	J	`jnl`	EF+EX Forest Algebras. CoRR Andreas Krebs, Howard Straubing
2014	—	`conf`	Extremely uniform branching programs. NCMA Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
2014	—	`conf`	From Ultrafilters on Words to the Expressive Power of a Fragment of Logic. DCFS Mai Gehrke, Andreas Krebs, Jean-Éric Pin
2014	J	`jnl`	Naive configurations. Des. Codes Cryptogr. Christoph Hering, Andreas Krebs, Thomas Edgar
2014	—	`conf`	Positive and Negative Proofs for Circuits and Branching Programs. DCFS Olga Dorzweiler, Thomas Flamm, Andreas Krebs, Michael Ludwig
2014	J	`jnl`	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. Matthias Maischak, Andreas Krebs, Ernst P. Stephan
2014	J	`jnl`	Skew Circuits of Small Width. Electron. Colloquium Comput. Complex. Nikhil Balaji, Andreas Krebs, Nutan Limaye
2014	J	`jnl`	Universal covers, color refinement, and two-variable logic with counting quantifiers: Lower bounds for the depth. CoRR Andreas Krebs, Oleg Verbitsky
2014	J	`jnl`	Visibly Counter Languages and Constant Depth Circuits. Electron. Colloquium Comput. Complex. Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig
2013	B	`conf`	Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy. CSL Christoph Berkholz, Andreas Krebs, Oleg Verbitsky
2013	—	`conf`	DLOGTIME Proof Systems. FSTTCS Andreas Krebs, Nutan Limaye
2013	J	`jnl`	Linear circuits, two-variable logic and weakly blocked monoids. Theor. Comput. Sci. Christoph Behle, Andreas Krebs, Mark Mercer
2013	B	`conf`	Small Depth Proof Systems. MFCS Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
2013	J	`jnl`	Small Depth Proof Systems. CoRR Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
2013	J	`jnl`	Small Depth Proof Systems. Electron. Colloquium Comput. Complex. Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
2013	—	`conf`	The Algebraic Theory of Parikh Automata. CAI Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
2013	J	`jnl`	The Algebraic Theory of Parikh Automata. Electron. Colloquium Comput. Complex. Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
2013	J	`jnl`	Verifying proofs in constant depth. ACM Trans. Comput. Theory Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer
2012	J	`jnl`	An effective characterization of the alternation hierarchy in two-variable logic CoRR Andreas Krebs, Howard Straubing
2012	—	`conf`	An effective characterization of the alternation hierarchy in two-variable logic. FSTTCS Andreas Krebs, Howard Straubing
2012	J	`jnl`	Counting Paths in VPA Is Complete for #NC 1. Algorithmica Andreas Krebs, Nutan Limaye, Meena Mahajan
2012	J	`jnl`	DLOGTIME-Proof Systems. Electron. Colloquium Comput. Complex. Andreas Krebs, Nutan Limaye
2012	C	`conf`	Dense Completeness. Developments in Language Theory Andreas Krebs, Klaus-Jörn Lange
2012	A*	`conf`	Non-definability of Languages by Generalized First-order Formulas over (N, +). LICS Andreas Krebs, A. V. Sreejith
2012	J	`jnl`	Non-definability of languages by generalized first-order formulas over (N,+) CoRR Andreas Krebs, A. V. Sreejith
2012	J	`jnl`	Streaming algorithms for recognizing nearly well-parenthesized expressions CoRR Andreas Krebs, Nutan Limaye, Srikanth Srinivasan
2012	J	`jnl`	The Complexity of Intersecting Finite Automata Having Few Final States. Electron. Colloquium Comput. Complex. Michael Blondin, Andreas Krebs, Pierre McKenzie
2012	B	`conf`	The Lower Reaches of Circuit Uniformity. MFCS Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie
2012	J	`jnl`	Verifying Proofs in Constant Depth. Electron. Colloquium Comput. Complex. Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer
2011	J	`jnl`	Low uniform versions of NC1. Electron. Colloquium Comput. Complex. Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie
2011	—	`conf`	Optimization of Quadrature Filters Based on the Numerical Integration of Improper Integrals. DAGM-Symposium Andreas Krebs, Johan Wiklund, Michael Felsberg
2011	J	`jnl`	Regular Languages in MAJ[>] with three variables. Electron. Colloquium Comput. Complex. Christoph Behle, Andreas Krebs
2011	B	`conf`	Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions. MFCS Andreas Krebs, Nutan Limaye, Srikanth Srinivasan
2011	—	`conf`	Typed Monoids - An Eilenberg-Like Theorem for Non Regular Languages. CAI Christoph Behle, Andreas Krebs, Stephanie Reifferscheid
2011	J	`jnl`	Typed Monoids - An Eilenberg-like Theorem for non regular Languages. Electron. Colloquium Comput. Complex. Christoph Behle, Andreas Krebs, Stephanie Reifferscheid
2010	J	`jnl`	A quadratic programming problem arising from the p-version for obstacle problems. Electron. Notes Discret. Math. Matthias Maischak, Andreas Krebs, Ernst P. Stephan
2010	Misc	`conf`	Counting Paths in VPA Is Complete for #NC COCOON Andreas Krebs, Nutan Limaye, Meena Mahajan
2010	J	`jnl`	Counting paths in VPA is complete for #NC Electron. Colloquium Comput. Complex. Andreas Krebs, Nutan Limaye, Meena Mahajan
2009	J	`jnl`	An Approach to characterize the Regular Languages in TC0 with Linear Wires. Electron. Colloquium Comput. Complex. Christoph Behle, Andreas Krebs, Stephanie Reifferscheid
2009	C	`conf`	Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG]. LATA Christoph Behle, Andreas Krebs, Stephanie Reifferscheid
2009	C	`conf`	Regular Languages Definable by Majority Quantifiers with Two Variables. Developments in Language Theory Christoph Behle, Andreas Krebs, Stephanie Reifferscheid
2008	—	`—`	Typed semigroups, majority logic, and threshold circuits. Andreas Krebs
2007	J	`jnl`	A Numerische Mathematik Andreas Krebs, Ernst P. Stephan
2007	J	`jnl`	A partial plane of order 6 constructed from the icosahedron. Des. Codes Cryptogr. Christoph Hering, Andreas Krebs
2007	J	`jnl`	Characterizing TC Theory Comput. Syst. Andreas Krebs, Klaus-Jörn Lange, Stephanie Reifferscheid
2007	A	`conf`	Languages with Bounded Multiparty Communication Complexity. STACS Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson, Denis Thérien
2007	B	`conf`	Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids. MFCS Christoph Behle, Andreas Krebs, Mark Mercer
2006	J	`jnl`	Languages with Bounded Multiparty Communication Complexity. Electron. Colloquium Comput. Complex. Arkadev Chattopadhyay, Michal Koucký, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien
2005	A	`conf`	Characterizing TC STACS Andreas Krebs, Klaus-Jörn Lange, Stephanie Reifferscheid
2003	J	`jnl`	Optimized Temporal Logic Compilation. J. Univers. Comput. Sci. Andreas Krebs, Jürgen Ruf