All reports by Author Yijia Chen:

__
TR13-065
| 21st April 2013
__

Yijia Chen, Joerg Flum#### On Limitations of the Ehrenfeucht-Fraisse-method in Descriptive Complexity

__
TR11-085
| 14th May 2011
__

Yijia Chen, Joerg Flum, Moritz Müller#### Hard instances of algorithms and proof systems

__
TR11-020
| 20th December 2010
__

Yijia Chen, Joerg Flum#### Listings and logics

__
TR10-008
| 13th January 2010
__

Yijia Chen, Joerg Flum#### On optimal proof systems and logics for PTIME

Revisions: 1

__
TR08-083
| 10th June 2008
__

Yijia Chen, Jörg Flum#### A logic for PTIME and a parameterized halting problem

__
TR07-137
| 6th November 2007
__

Yijia Chen, Jörg Flum, Moritz Müller#### Lower Bounds for Kernelizations

__
TR07-106
| 10th September 2007
__

Yijia Chen, Martin Grohe, Magdalena Grüber#### On Parameterized Approximability

__
TR06-011
| 2nd January 2006
__

Yijia Chen, Martin Grohe#### An Isomorphism between Subexponential and Parameterized Complexity Theory

Yijia Chen, Joerg Flum

Ehrenfeucht-Fraisse games and their generalizations have been quite successful in finite model theory and yield various inexpressibility results. However, for key problems such as P $\ne$ NP or NP $\ne$ coNP no progress has been achieved using the games. We show that for these problems it is already hard to ... more >>>

Yijia Chen, Joerg Flum, Moritz Müller

Assuming that the class TAUT of tautologies of propositional logic has no almost optimal algorithm, we show that every algorithm $\mathbb A$ deciding TAUT has a polynomial time computable sequence witnessing that $\mathbb A$ is not almost optimal. The result extends to every $\Pi_t^p$-complete problem with $t\ge 1$; however, we ... more >>>

Yijia Chen, Joerg Flum

There are standard logics DTC, TC, and LFP capturing the complexity classes L, NL, and P on ordered structures, respectively. In [Chen and Flum, 2010] we have shown that ${\rm LFP}_{\rm inv}$, the ``order-invariant least fixed-point logic LFP,'' captures P (on all finite structures) if and only if there is ... more >>>

Yijia Chen, Joerg Flum

We prove that TAUT has a $p$-optimal proof system if and only if $L_\le$, a logic introduced in [Gurevich, 88], is a P-bounded logic for P. Furthermore, using the method developed in [Chen and Flum, 10], we show that TAUT has no \emph{effective} $p$-optimal proof system under some reasonable complexity-theoretic ... more >>>

Yijia Chen, Jörg Flum

In [Blass, Gurevich, and Shelah, 99] a logic L_Y has been introduced as a possible candidate for a logic capturing the PTIME properties of structures (even in the absence of an ordering of their universe). A reformulation of this problem in terms of a parameterized halting problem p-Acc for nondeterministic ... more >>>

Yijia Chen, Jörg Flum, Moritz Müller

Among others, refining the methods of [Fortnow and Santhanam, ECCC Report TR07-096] we improve a result of this paper and show for any parameterized problem with a ``linear weak OR'' and with NP-hard underlying classical problem that there is no polynomial reduction from the problem to itself that assigns to ... more >>>

Yijia Chen, Martin Grohe, Magdalena Grüber

Combining classical approximability questions with parameterized complexity, we introduce a theory of parameterized approximability.

The main intention of this theory is to deal with the efficient approximation of small cost solutions for optimisation problems.

Yijia Chen, Martin Grohe

We establish a close connection between (sub)exponential time complexity and parameterized complexity by proving that the so-called miniaturization mapping is a reduction preserving isomorphism between the two theories.

more >>>