Yijia Chen

Mingjun Liu

CoRR, July, 2025

A Parameterized Halting Problem, $ \Delta _0$ Truth and the Mrdp Theorem.

[BibT_eX]

[DOI]

Keita Yokoyama

J. Symb. Log., 2025

On Average Baby PIH and Its Applications.

[BibT_eX]

[DOI]

Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025

Simple Combinatorial Construction of the ko (1)-Lower Bound for Approximating the Parameterized k-Clique.

[BibT_eX]

[DOI]

Proceedings of the 2025 Symposium on Simplicity in Algorithms, 2025

2023

Simple Combinatorial Construction of the ko(1)-Lower Bound for Approximating the Parameterized k-Clique.

[BibT_eX]

[DOI]

CoRR, 2023

2022

A Surprising Relationship Between Descriptive Complexity and Proof Complexity.

[BibT_eX]

[DOI]

Bull. EATCS, 2022

A parameterized halting problem, Δ0 truth and the MRDP theorem.

[BibT_eX]

[DOI]

Keita Yokoyama

CoRR, 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

Forbidden Induced Subgraphs and the Łoś-Tarski Theorem.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 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

The parameterized space complexity of model-checking bounded variable first-order logic.

[BibT_eX]

[DOI]

Michael Elberfeld

Log. Methods Comput. Sci., 2019

Some lower bounds in parameterized AC0.

[BibT_eX]

[DOI]

Inf. Comput., 2019

The Complexity of Homomorphism Indistinguishability.

[BibT_eX]

[DOI]

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

2018

A parameterized halting problem, the linear time hierarchy, and the MRDP theorem.

[BibT_eX]

[DOI]

Keita Yokoyama

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 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

The Complexity of Limited Belief Reasoning - The Quantifier-Free Case.

[BibT_eX]

[DOI]

Abdallah Saffidine

Christoph Schwering

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

2017

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

[BibT_eX]

[DOI]

Rodney G. Downey

NII Shonan Meet. Rep., 2017

The Hardness of Embedding Grids and Walls.

[BibT_eX]

[DOI]

Bingkai Lin

Proceedings of the Graph-Theoretic Concepts in Computer Science, 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

The Constant Inapproximability of the Parameterized Dominating Set Problem.

[BibT_eX]

[DOI]

Bingkai Lin

Proceedings of the IEEE 57th Annual Symposium on 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

Bounded Variable Logic, Parameterized Logarithmic Space, and Savitch's Theorem.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2014, 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

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

The Parameterized Complexity of k-Edge Induced Subgraphs.

[BibT_eX]

[DOI]

Bingkai Lin

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Hard Instances of Algorithms and Proof Systems.

[BibT_eX]

[DOI]

Proceedings of the How the World Computes, 2012

A Parameterized Halting Problem.

[BibT_eX]

[DOI]

Proceedings of the Multivariate Algorithmic Revolution and Beyond, 2012

2011

Strong isomorphism reductions in complexity theory.

[BibT_eX]

[DOI]

J. Symb. Log., 2011

Listings and Logics.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, 2011

Consistency and Optimality.

[BibT_eX]

[DOI]

Proceedings of the Models of Computation in Context, 2011

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

A Logic for PTIME and a Parameterized Halting Problem.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, 2009

Lower Bounds for Kernelizations and Other Preprocessing Procedures.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Theory and Computational Practice, 2009

2008

Understanding the Complexity of Induced Subgraph Isomorphisms.

[BibT_eX]

[DOI]

Marc Thurley

Mark Weyer

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 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

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

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 21st International Workshop, 2007

On Parameterized Path and Chordless Path Problems.

[BibT_eX]

[DOI]

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

2006

On Parameterized Approximability.

[BibT_eX]

[DOI]

Magdalena Grüber

Proceedings of the Parameterized and Exact Computation, Second International Workshop, 2006

The Parameterized Complexity of Maximality and Minimality Problems.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation, Second International Workshop, 2006

An Isomorphism between Subexponential and Parameterized Complexity Theory.

[BibT_eX]

[DOI]

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

Machine-based methods in parameterized complexity theory.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

2004

Model-checking problems, machines and parameterized complexity.

[BibT_eX]

[DOI]

PhD thesis, 2004

On Miniaturized Problems in Parameterized Complexity Theory.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation, First International Workshop, 2004

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

2000

The Downward Transfer of Elementary Satisfiability of Partition Logics.

[BibT_eX]

[DOI]

Enshao Shen