EATCSIPEC Nerode Prize 2014  LaudatioOn 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 Widmayer (ETH Zurich, Switzerland; chair), has unanimously decided to award Hans L. Bodlaender (Utrecht University, The Netherlands), Rodney G. Downey (Victoria University of Wellington, New Zealand), Michael R. Fellows (Charles Darwin University, Australia), Danny Hermelin (BenGurion University of the Negev, Israel), Lance Fortnow (Georgia Institute of Technology, USA), and Rahul Santhanam (University of Edinburgh, Scotland) the 2014 EATCSIPEC 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 polynomialtime 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 algorithm for parameterized problems. The second paper proves that the existence of a distillation algorithm for any NPcomplete problem would imply a collapse of the polynomial hierarchy to the third level. This shows a vital connection between parameterized complexity and a classical complexitytheoretic 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.
