Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Moritz Müller:

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

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

ISSN 1433-8092 | Imprint