EATCS-IPEC Nerode Prize 2014 - Laudatio
On problems without polynomial kernels, Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin
Infeasibility of instance compression and succinct PCPs for NP, Lance Fortnow, Rahul Santhanam, Journal of Computer and System Sciences, 2011
The Nerode Prize 2014 Committee, consisting of Georg Gottlob (University of Oxford, UK), Jan Arne Telle (University of Bergen, Norway), and Peter Wid-mayer (ETH Zurich, Switzerland; chair), has unanimously decided to award Hans L. Bodlaender (Utrecht University, The Netherlands), Rodney G. Downey (Victo-ria University of Wellington, New Zealand), Michael R. Fellows (Charles Darwin University, Australia), Danny Hermelin (Ben-Gurion University of the Negev, Israel), Lance Fortnow (Georgia Institute of Technology, USA), and Rahul San-thanam (University of Edinburgh, Scotland) the 2014 EATCS-IPEC Nerode Prize for outstanding papers in the area of multivariate algorithmics.
Their two papers provide the mathematical framework establishing the ﬁeld of kernelization algorithms as a rigorous theory having both upper and lower bounds. Parameterized problems in the complexity class FPT have kernelization algorithms, a polynomial-time preprocessing that reduces any given instance to an equivalent kernel instance whose size depends only on the parameter value. If this dependence is polynomial we have a polynomial kernel. Together, the two outstanding papers by the prize winners show that many problems in FPT do not have a polynomial kernel unless the polynomial hierarchy collapses to the third level. The ﬁrst paper introduces the key notions to make this connection, in the form of a distillation algorithm for classical problems and of a composition algo-rithm for parameterized problems. The second paper proves that the existence of a distillation algorithm for any NP-complete problem would imply a collapse of the polynomial hierarchy to the third level. This shows a vital connection be-tween parameterized complexity and a classical complexity-theoretic hypothesis. Altogether, these results and tools have paved the way for a disciplined and useful mathematical study of the major practical computing strategy of preprocessing.