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

__
TR07-137
| 6th November 2007
__

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

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