ECCC-Report TR07-137https://eccc.weizmann.ac.il/report/2007/137Comments and Revisions published for TR07-137en-usSat, 29 Dec 2007 02:58:04 +0200
Paper TR07-137
| Lower Bounds for Kernelizations |
Yijia Chen,
Jörg Flum,
Moritz Müller
https://eccc.weizmann.ac.il/report/2007/137Among 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).
Sat, 29 Dec 2007 02:58:04 +0200https://eccc.weizmann.ac.il/report/2007/137