Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > KERNELIZATION LOWER BOUNDS:
Reports tagged with Kernelization Lower Bounds:
TR11-072 | 1st May 2011
Danny Hermelin, Xi Wu

Weak Compositions and Their Applications to Polynomial Lower-Bounds for Kernelization

Revisions: 1

We introduce a new form of composition called \emph{weak composition} that allows us to obtain polynomial kernelization lower-bounds for several natural parameterized problems. Let $d \ge 2$ be some constant and let $L_1, L_2 \subseteq \{0,1\}^* \times \N$ be two parameterized problems where the unparameterized version of $L_1$ is \NP-hard. ... more >>>




ISSN 1433-8092 | Imprint