2024
Forbidden induced subgraphs and the łOś-Tarski Theorem.
J. Symb. Log., 2024
2022
A Surprising Relationship Between Descriptive Complexity and Proof Complexity.
Bull. EATCS, 2022
On Algorithms Based on Finitely Many Homomorphism Counts.
Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022
2021
On Queries Determined by a Constant Number of Homomorphism Counts.
CoRR, 2021
2020
FO-Definability of Shrub-Depth.
Proceedings of the 28th EACSL Annual Conference on Computer Science Logic, 2020
Parameterized Parallel Computing and First-Order Logic.
Proceedings of the Fields of Logic and Computation III, 2020
2019
Some lower bounds in parameterized AC<sup>0</sup>.
Inf. Comput., 2019
2018
Tree-depth, quantifier elimination, and quantifier rank.
Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018
2017
Logic and Computational Complexity (NII Shonan Meeting 2017-13).
NII Shonan Meet. Rep., 2017
Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.
Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, 2017
2016
Some Lower Bounds in Parameterized AC^0.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016
2015
The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture.
Proceedings of the Fields of Logic and Computation II, 2015
2014
2013
On Limitations of the Ehrenfeucht-Fraisse-method in Descriptive Complexity.
Electron. Colloquium Comput. Complex., 2013
Consistency, optimality, and incompleteness.
Ann. Pure Appl. Log., 2013
2012
From Almost Optimal Algorithms to Logics for Complexity Classes via Listings and a Halting Problem.
J. ACM, 2012
Some definitorial suggestions for parameterized proof complexity.
Electron. Colloquium Comput. Complex., 2012
On the Ordered Conjecture.
Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, 2012
The Exponential Time Hypothesis and the Parameterized Clique Problem.
Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012
A Parameterized Halting Problem.
Proceedings of the Multivariate Algorithmic Revolution and Beyond, 2012
2011
Lower Bounds for Kernelizations and Other Preprocessing Procedures.
Theory Comput. Syst., 2011
Strong isomorphism reductions in complexity theory.
J. Symb. Log., 2011
Hard instances of algorithms and proof systems.
Electron. Colloquium Comput. Complex., 2011
Electron. Colloquium Comput. Complex., 2011
Invariantization of Listings.
Proceedings of the Mathematical Foundations of Computer Science 2011, 2011
Consistency and Optimality.
Proceedings of the Models of Computation in Context, 2011
2010
W-Hierarchies Defined by Symmetric Gates.
Theory Comput. Syst., 2010
On the complexity of Gödel's proof predicate.
J. Symb. Log., 2010
On optimal proof systems and logics for PTIME.
Electron. Colloquium Comput. Complex., 2010
On <i>p</i>-Optimal Proof Systems and Logics for PTIME.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010
On Slicewise Monotone Parameterized Problems and Optimal Proof Systems for TAUT.
Proceedings of the Computer Science Logic, 24th International Workshop, 2010
2009
Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping.
J. Log. Comput., 2009
2008
A logic for PTIME and a parameterized halting problem.
Electron. Colloquium Comput. Complex., 2008
The parameterized complexity of maximality and minimality problems.
Ann. Pure Appl. Log., 2008
2007
An analysis of the W<sup>*</sup>-hierarchy.
J. Symb. Log., 2007
Lower Bounds for Kernelizations.
Electron. Colloquium Comput. Complex., 2007
Bounded fixed-parameter tractability and reducibility.
Ann. Pure Appl. Log., 2007
On Parameterized Path and Chordless Path Problems.
Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007
Parameterized Complexity and Logic.
Proceedings of the Computation and Logic in the Real World, 2007
Einführung in die mathematische Logik (5. Aufl.).
Spektrum Akademischer Verlag, 2007
2006
Parameterized Complexity Theory
Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-540-29953-0, 2006
On miniaturized problems in parameterized complexity theory.
Theor. Comput. Sci., 2006
Bounded fixed-parameter tractability and log<sup>2</sup><i>n</i> nondeterministic bits.
J. Comput. Syst. Sci., 2006
2005
Machine-based methods in parameterized complexity theory.
Theor. Comput. Sci., 2005
Model-checking problems as a basis for parameterized intractability.
Log. Methods Comput. Sci., 2005
2004
The Parameterized Complexity of Counting Problems.
SIAM J. Comput., 2004
Parametrized Complexity and Subexponential Time (Column: Computational Complexity).
Bull. EATCS, 2004
Bounded Fixed-Parameter Tractability and log<sup>2</sup>n Nondeterministic Bits.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004
2003
Describing parameterized complexity classes.
Inf. Comput., 2003
Machine Characterization of the Classes of the W-Hierarchy.
Proceedings of the Computer Science Logic, 17th International Workshop, 2003
Bounded Nondeterminism and Alternation in Parameterized Complexity Theory.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003
2002
Query evaluation via tree-decompositions.
J. ACM, 2002
2001
Fixed-Parameter Tractability, Definability, and Model-Checking.
SIAM J. Comput., 2001
Tree-Decompositions and the Model-Checking Problem.
Bull. EATCS, 2001
2000
Games and total Datalog¬ queries.
Theor. Comput. Sci., 2000
Games, Kernels, and Antitone Operations.
Order, 2000
On Fixed-Point Logic With Counting.
J. Symb. Log., 2000
1999
Quantifiers and Congruence Closure.
Stud Logica, 1999
Pseudo-Finite Homogeneity and Saturation.
J. Symb. Log., 1999
1998
An Extension of the Lemma of Rasiowa and Sikorski.
Math. Log. Q., 1998
1997
Total and Partial Well-Founded Datalog Coincide.
Proceedings of the Database Theory, 1997
1996
Einführung in die mathematische Logik (4. Aufl.).
Hochschultaschenbuch, Spektrum Akadem. Verl., ISBN: 978-3-8274-0130-4, 1996
1995
Perspectives in Mathematical Logic, Springer, ISBN: 978-3-540-60149-4, 1995
1994
Mathematical logic (2. ed.).
Undergraduate texts in mathematics, Springer, ISBN: 978-3-540-94258-0, 1994
1992
Einführung in die mathematische Logik (3. Aufl.).
BI-Wissenschaftsverlag, ISBN: 978-3-411-15603-0, 1992
1991
Proceedings of the Computer Science Logic, 5th Workshop, 1991
1988
On Topological Spaces Equivalent to Ordinals.
J. Symb. Log., 1988
1985
χ-Local Operations for Topological Structures.
Math. Log. Q., 1985
Maximale monadische Logiken.
Arch. Math. Log., 1985
1984
Undergraduate texts in mathematics, Springer, ISBN: 978-0-387-90895-3, 1984
1975
L(Q)-Preservation Theorems.
J. Symb. Log., 1975
1971
A Remark on Infinitary Languages.
J. Symb. Log., 1971