Jörg Flum

J. Symb. Log., 2024

2022

A Surprising Relationship Between Descriptive Complexity and Proof Complexity.

[BibT_eX]

[DOI]

Bull. EATCS, 2022

On Algorithms Based on Finitely Many Homomorphism Counts.

[BibT_eX]

[DOI]

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

2021

On Queries Determined by a Constant Number of Homomorphism Counts.

[BibT_eX]

[DOI]

CoRR, 2021

2020

FO-Definability of Shrub-Depth.

[BibT_eX]

[DOI]

Proceedings of the 28th EACSL Annual Conference on Computer Science Logic, 2020

Parameterized Parallel Computing and First-Order Logic.

[BibT_eX]

[DOI]

Proceedings of the Fields of Logic and Computation III, 2020

2019

Some lower bounds in parameterized AC0.

[BibT_eX]

[DOI]

Inf. Comput., 2019

2018

Tree-depth, quantifier elimination, and quantifier rank.

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

2017

Logic and Computational Complexity (NII Shonan Meeting 2017-13).

[BibT_eX]

[DOI]

Rodney G. Downey

NII Shonan Meet. Rep., 2017

Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.

[BibT_eX]

[DOI]

Xuangui Huang

Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, 2017

2016

Some Lower Bounds in Parameterized AC^0.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015

The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture.

[BibT_eX]

[DOI]

Proceedings of the Fields of Logic and Computation II, 2015

2014

On Optimal Inverters.

[BibT_eX]

[DOI]

Bull. Symb. Log., 2014

2013

On Limitations of the Ehrenfeucht-Fraisse-method in Descriptive Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Consistency, optimality, and incompleteness.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2013

2012

From Almost Optimal Algorithms to Logics for Complexity Classes via Listings and a Halting Problem.

[BibT_eX]

[DOI]

J. ACM, 2012

Some definitorial suggestions for parameterized proof complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

On the Ordered Conjecture.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, 2012

The Exponential Time Hypothesis and the Parameterized Clique Problem.

[BibT_eX]

[DOI]

Kord Eickmeyer

Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

A Parameterized Halting Problem.

[BibT_eX]

[DOI]

Proceedings of the Multivariate Algorithmic Revolution and Beyond, 2012

2011

Lower Bounds for Kernelizations and Other Preprocessing Procedures.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

Strong isomorphism reductions in complexity theory.

[BibT_eX]

[DOI]

J. Symb. Log., 2011

Hard instances of algorithms and proof systems.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Listings and logics.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Invariantization of Listings.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Consistency and Optimality.

[BibT_eX]

[DOI]

Proceedings of the Models of Computation in Context, 2011

2010

W-Hierarchies Defined by Symmetric Gates.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

On the complexity of Gödel's proof predicate.

[BibT_eX]

[DOI]

J. Symb. Log., 2010

On optimal proof systems and logics for PTIME.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

On p-Optimal Proof Systems and Logics for PTIME.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

On Slicewise Monotone Parameterized Problems and Optimal Proof Systems for TAUT.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 24th International Workshop, 2010

2009

Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping.

[BibT_eX]

[DOI]

J. Log. Comput., 2009

2008

A logic for PTIME and a parameterized halting problem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

The parameterized complexity of maximality and minimality problems.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2008

2007

An analysis of the W*-hierarchy.

[BibT_eX]

[DOI]

J. Symb. Log., 2007

Lower Bounds for Kernelizations.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Bounded fixed-parameter tractability and reducibility.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2007

On Parameterized Path and Chordless Path Problems.

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

Parameterized Complexity and Logic.

[BibT_eX]

[DOI]

Proceedings of the Computation and Logic in the Real World, 2007

Einführung in die mathematische Logik (5. Aufl.).

[BibT_eX]

Spektrum Akademischer Verlag, 2007

2006

Parameterized Complexity Theory

[BibT_eX]

[DOI]

Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-540-29953-0, 2006

On miniaturized problems in parameterized complexity theory.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2006

Bounded fixed-parameter tractability and log2n nondeterministic bits.

[BibT_eX]

[DOI]

Mark Weyer

J. Comput. Syst. Sci., 2006

2005

Machine-based methods in parameterized complexity theory.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Model-checking problems as a basis for parameterized intractability.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2005

2004

The Parameterized Complexity of Counting Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2004

Parametrized Complexity and Subexponential Time (Column: Computational Complexity).

[BibT_eX]

Bull. EATCS, 2004

Bounded Fixed-Parameter Tractability and log2n Nondeterministic Bits.

[BibT_eX]

[DOI]

Mark Weyer

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003

Describing parameterized complexity classes.

[BibT_eX]

[DOI]

Inf. Comput., 2003

Machine Characterization of the Classes of the W-Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 17th International Workshop, 2003

Bounded Nondeterminism and Alternation in Parameterized Complexity Theory.

[BibT_eX]

[DOI]

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Query evaluation via tree-decompositions.

[BibT_eX]

[DOI]

Markus Frick

J. ACM, 2002

2001

Fixed-Parameter Tractability, Definability, and Model-Checking.

[BibT_eX]

[DOI]

SIAM J. Comput., 2001

Tree-Decompositions and the Model-Checking Problem.

[BibT_eX]

Bull. EATCS, 2001

2000

Games and total Datalog¬ queries.

[BibT_eX]

[DOI]

Max Kubierschky

Bertram Ludäscher

Theor. Comput. Sci., 2000

Games, Kernels, and Antitone Operations.

[BibT_eX]

[DOI]

Order, 2000

On Fixed-Point Logic With Counting.

[BibT_eX]

[DOI]

J. Symb. Log., 2000

1999

Quantifiers and Congruence Closure.

[BibT_eX]

[DOI]

Matthias Schiehlen

Jouko A. Väänänen

Stud Logica, 1999

Pseudo-Finite Homogeneity and Saturation.

[BibT_eX]

[DOI]

Martin Ziegler

J. Symb. Log., 1999

1998

An Extension of the Lemma of Rasiowa and Sikorski.

[BibT_eX]

[DOI]

Math. Log. Q., 1998

1997

Total and Partial Well-Founded Datalog Coincide.

[BibT_eX]

[DOI]

Max Kubierschky

Bertram Ludäscher

Proceedings of the Database Theory, 1997

1996

Einführung in die mathematische Logik (4. Aufl.).

[BibT_eX]

Hochschultaschenbuch, Spektrum Akadem. Verl., ISBN: 978-3-8274-0130-4, 1996

1995

Finite model theory.

[BibT_eX]

Perspectives in Mathematical Logic, Springer, ISBN: 978-3-540-60149-4, 1995

1994

Mathematical logic (2. ed.).

[BibT_eX]

Undergraduate texts in mathematics, Springer, ISBN: 978-3-540-94258-0, 1994

1992

Einführung in die mathematische Logik (3. Aufl.).

[BibT_eX]

BI-Wissenschaftsverlag, ISBN: 978-3-411-15603-0, 1992

1991

On Bounded Theories.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 5th Workshop, 1991

1988

On Topological Spaces Equivalent to Ordinals.

[BibT_eX]

[DOI]

Juan Carlos Martínez

J. Symb. Log., 1988

1985

χ-Local Operations for Topological Structures.

[BibT_eX]

[DOI]

Juan Carlos Martínez

Math. Log. Q., 1985

Maximale monadische Logiken.

[BibT_eX]

[DOI]

Arch. Math. Log., 1985

1984

Mathematical logic.

[BibT_eX]

Undergraduate texts in mathematics, Springer, ISBN: 978-0-387-90895-3, 1984

1975

L(Q)-Preservation Theorems.

[BibT_eX]

[DOI]

J. Symb. Log., 1975

1971

A Remark on Infinitary Languages.

[BibT_eX]

[DOI]