A parameterized halting problem, the linear time hierarchy, and the MRDP theorem (with Moritz Müller and Keita Yokoyama).

Conference version to appear in

Tree-depth, quantifier elimination, and quantifier rank (with Jörg Flum).

Conference version to appear in

The complexity of limited belief reasoning - the quantifier-free case (with Abdallah Saffidine and Christoph Schwering).

Conference version to appear in

Slicewise definability in first-order logic with bounded quantifier rank (with Jörg Flum and Xuangui Huang).

Conference version appeared in

The hardness of embedding grids and walls (with Martin Grohe and Bingkai Lin).

Conference version appeared in

Lecture Notes in Computer Science 10520, pp. 180-192, 2017.

The parameterized complexity of

Conference version appeared in

Lecture Notes in Computer Science 7391, pp. 641-652, 2012.

The constant inapproximability of the parameterized dominating set problem (with Bingkai Lin).

Conference version appeared in

Some lower bounds in parameterized AC

Conference version appeared in

The Ehrenfeucht-Fraïssé method and the planted clique conjecture (with Jörg Flum).

In

Lecture Notes in Computer Science 9300, pp. 87-108, 2015.

Counting problems in parameterized complexity (with Chihao Zhang).

Bounded variable logic, parameterized logarithmic space, and Savitch's theorem (with Moritz Müller).

Conference version appeared in

Lecture Notes in Computer Science 8634, pp.183-195, 2014.

Hard instances of algorithms and proof systems (with Jörg Flum and Moritz Müller).

Conference version appeared in

Lecture Notes in Computer Science 7318, pp. 118-128, 2012.

On optimal inverters (with Jörg Flum).

Consistency, optimality, and incompleteness (with Jörg Flum and Moritz Müller).

Conference version appeared in

Lecture Notes in Computer Science 6735, pp. 61-70, 2011.

On limitations of the Ehrenfeucht-Fraïssé-method in descriptive complexity (with Jörg Flum).

The exponential time hypothesis and the parameterized clique problem (with Jörg Flum and Kord Eickmeyer).

Conference version appeared in

Lecture Notes in Computer Science 7535, pp.13-24, 2012.

From almost optimal algorithms to logics for complexity classes via listings and a halting problem (with Jörg Flum).

On the ordered conjecture (with Jörg Flum).

Conference version appeared in

A parameterized halting problem (with Jörg Flum).

In

Lecture Notes in Computer Science 7370, pp. 364-397, 2012.

Strong isomorphism reductions in complexity theory (with Sam Buss, Jörg Flum, Sy Friedman, and Moritz Müller).

Listings and logics (with Jörg Flum).

Conference version appeared in

Lower bounds for kernelizations and other preprocessing procedures (with Jörg Flum and Moritz Müller).

Conference version appeared in

Lecture Notes in Computer Science 5635, pp. 118-128, 2009.

On slicewise monotone parameterized problems and optimal proof Systems for TAUT (with Jörg Flum).

Conference version appeared in

Lecture Notes in Computer Science 6247, pp. 200-214, 2010.

On

Conference version appeared in

Lecture Notes in Computer Science 6199, pp. 321-332, 2010.

On the complexity of Gödel's proof predicate (with Jörg Flum).

A logic for PTIME and a parameterized halting problem (with Jörg Flum).

Conference version appeared in

Subexponential time and fixed-parameter tractability: exploiting the miniaturization mapping (with Jörg Flum).

Conference version appeared in

Lecture Notes in Computer Science 4646, pp. 389-404, 2007.

Understand the complexity of induced subgraph isomorphisms (with Marc Thurley and Mark Weyer).

Conference version appeared in

Lecture Notes in Computer Science 5125, pp.587-596,2008.

The slides of my FPT 2008 talk based on this paper.

The parameterized complexity of maximality and minimality problems (with Jörg Flum).

Conference version appeared in

Lecture Notes in Computer Science 4169, pp.25-37, 2006.

An isomorphism between subexponential and parameterized complexity theory (with Martin Grohe).

A partial version appeared as

Conference version appeared in

On parameterized approximability (with Martin Grohe and Magdalena Grüber).

Conference version appeared in

Lecture Notes in Computer Science 4169, pp.109-120, 2006.

On parameterized path and chordless path problems (with Jörg Flum).

Conference version appeared in

An analysis of the W*-hierarchy (with Jörg Flum and Martin Grohe).

On miniaturized problems in parameterized complexity theory (with Jörg Flum).

Conference version appeared in

Lecture Notes in Computer Science 3162, pp.108-120, 2004.

Machine-based methods in parameterized complexity (with Jörg Flum and Martin Grohe).

Machine characterizations of the classes of the W-hierarchy (with Jörg Flum).

Conference version appeared in

Lecture Notes in Computer Science 2803, pp. 114-127, 2003.

Bounded nondeterminism and alternation in parameterized complexity theory (with Jörg Flum and Martin Grohe).

Conference version appeared in

Capture complexity by partition (with Enshao Shen).

Conference version appeared in

Lecture Notes in Computer Science 2142, pp. 84-98, 2001.

The downward transfer of elementary satisfiability of partition logics (with Enshao Shen).