Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-137 | 6th November 2007 00:00

Lower Bounds for Kernelizations

RSS-Feed




TR07-137
Authors: Yijia Chen, Jörg Flum, Moritz Müller
Publication: 29th December 2007 02:58
Downloads: 1725
Keywords: 


Abstract:

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 every instance $x$ with parameter $k$ an instance $y$ with $|y| = k^{O(1)} \cdot |x|^{1-\epsilon}$ unless the polynomial hierarchy collapses to its third level (here $\epsilon$ is any given real number greater than zero).



ISSN 1433-8092 | Imprint