Nerode Prize

Winners

• 2013: Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi, and Francis Zane, for their research formulating the exponential time hypothesis and using it to determine the exact parameterized complexity of several important variants of the Boolean satisfiability problem.
• 2014: Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin, Lance Fortnow, and Rahul Santhanam, for their work on kernelization, proving that several problems with fixed-parameter tractable algorithms do not have polynomial-size kernels unless the polynomial hierarchy collapses.
• 2015: Erik Demaine, Fedor V. Fomin, Mohammad Hajiaghayi, and Dimitrios Thilikos, for their research on bidimensionality, defining a broad framework for the design of fixed-parameter-tractable algorithms for domination and covering problems on graphs.
• 2016: Andreas Björklund for his paper Determinant Sums for Undirected Hamiltonicity, showing that methods based on algebraic graph theory lead to a significantly improved algorithm for finding Hamiltonian cycles
• 2017: Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch, for developing the "measure and conquer" method for the analysis of backtracking algorithms.
• 2018: Stefan Kratsch and Magnus Wahlström for their work using matroid theory to develop polynomial-size kernels for odd cycle transversal and related problems.
• 2019: Noga Alon, Raphael Yuster, and Uri Zwick, for inventing Color-coding technique, a vastly important ingredient in the toolbox of parameterized algorithm design.