On problems without polynomial kernels

By Hans L. Bodlaender, R. Downey, M. Fellows, Danny Hermelin. Journal of computer and system sciences (Print), 2009

537 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Infeasibility of instance compression and succinct PCPs for NP (2007, unknown): “[4] and Harnik and Naor [15] raise the following question, which has relevance to a wide variety of areas, including parameterized complexity, cryptography, probabilistically checkable proofs and structural complexity.”
(Meta) Kernelization (2009, background): “For instance, even though the problem of finding a path of length k is expressible in first order logic, it does not admit a polynomial kernel on planar graphs, unless polynomial hierarchy collapses to the third level, a collapse which is deemed unlikely [7].”