Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR11-085 | 14th May 2011
Yijia Chen, Joerg Flum, Moritz Müller

Hard instances of algorithms and proof systems

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

TR11-020 | 20th December 2010
Yijia Chen, Joerg Flum

Listings and logics

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

TR10-008 | 13th January 2010
Yijia Chen, Joerg Flum

On optimal proof systems and logics for PTIME

Revisions: 1

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

TR08-083 | 10th June 2008
Yijia Chen, Jörg Flum

A logic for PTIME and a parameterized halting problem

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

TR07-137 | 6th November 2007
Yijia Chen, Jörg Flum, Moritz Müller

Lower Bounds for Kernelizations

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

TR07-106 | 10th September 2007
Yijia Chen, Martin Grohe, Magdalena Grüber

On Parameterized Approximability

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.

more >>>

TR06-011 | 2nd January 2006
Yijia Chen, Martin Grohe

An Isomorphism between Subexponential and Parameterized Complexity Theory

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

ISSN 1433-8092 | Imprint