The EATCS-IPEC Nerode Prize for outstanding papers in the area of multivariate algorithmics is awarded annually at IPEC, the International Symposium on Parameterized and Exact Computation.
History
The EATCS-IPEC Nerode Prize for outstanding papers in the area of multivariate algorithmics. The Prize is named in honor of Anil Nerode, in recognition of his major contributions to mathematical logic, theory of automata, computability, and complexity theory. It has been awarded annually since 2013, with the presentation taking place during IPEC (International Symposium on Parameterized and Exact Computation). The list of prize winners follows below and can also be found at the EATCS website on the EATCS-IPEC Nerode Prize.
Eligibility
Any research paper or series of research papers by a single author or by a team of authors published in a recognized refereed journal is eligible. The research work nominated for the award should be in the area of multivariate algorithms and complexity meant in a broad sense, and encompasses, but is not restricted to, those areas covered by IPEC. The Award Committee has the ultimate authority to decide on the eligibility of a nomination. Papers authored by a member of the Award Committee are not eligible for nomination.
In the past, the year of publication was restricted (at least two years and at most ten years before the year of the award nomination). This restriction has been removed.
Nominations
Nominations may be made by any member of the scientific community including the members of the Award Committee. A nomination should contain a brief summary of the technical content of each nominated paper and a brief explanation of its significance. Nominations are done by an email to the Award Committee Chair with copies to the members of the committee.
Award Committee
The award committee consists of three members. Each member serves three years. Each year, a new member is nominated by the IPEC Steering Committee. The committee member that is in their third year is the chair of the committee.
Award Committee 2024-2025
The award committee for the 2024-2025 EATCS-IPEC Nerode Prize consisted of:
- Sang-il Oum (2022-2025, chair)
- Russell Impagliazzo (2023-2026)
- Michał Pilipczuk (2024-2027)
Former Committee Members
- Rolf Niedermeier (2012-2013)
- Peter Widmayer (2012-2014)
- Georg Gottlob (2012-2015)
- Jan Arne Telle (2013-2016)
- David Eppstein (2014-2017)
- Dániel Marx (2015-2018)
- Jianer Chen (2016-2019)
- Hans L. Bodlaender (2017-2020)
- Virginia Vassilevska Williams (2018-2021)
- Anuj Dawar (2019-2022)
- Fedor V. Fomin (2020-2023)
- Thore Husfeldt (2021-2024)
Winners
Laudations for all winners can be found on the official website of the EATCS-IPEC Nerode Prize
2025
Jaroslav Nešetřil and Patrice Ossona de Mendez for the papers:
- "Grad and classes with bounded expansion I. Decompositions", European Journal of Combinatorics 29(3):760–776, 2008;
- "Grad and classes with bounded expansion II. Algorithmic aspects", European Journal of Combinatorics 29(3):777–791, 2008;
- "First order properties on nowhere dense structures", Journal of Symbolic Logic, 75(3):868–887, 2010;
- "On nowhere dense graphs", European Journal of Combinatorics 32(4):600–617, 2011.
Committee: Sang-il Oum (chair), Russell Impagliazzo, Michał Pilipczuk.
2024
Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos for the paper:
- "(Meta) Kernelization", Journal of the ACM 63(5):44:1-44:69, 2016. Announced at IEEE Foundations of Computer Science (FOCS) 2010.
Commitee: Thore Husfeldt (chair), Sang-il Oum, Russell Impagliazzo.
2023
Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk for the paper:
- "Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time", ACM Transactions on Algorithms 18(2):17:1-17:31, 2022. Announced at IEEE Foundations of Computer Science (FOCS) 2011.
Committee: Fedor V. Fomin (chair), Thore Husfeldt, Sang-il Oum.
2022
Bruno Courcelle for his papers:
- "The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs", Inf. Comput. 85(1):12-75, 1990;
- "The Monadic Second-Order Logic of Graphs III: Tree-Decompositions, Minors and Complexity Issues", RAIRO Theor. Informatics Appl. 26:257-286, 1992.
Committee: Anuj Dawar (chair), Fedor V. Fomin, Thore Husfeldt.
2021
Cristian Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan for their paper:
- "Deciding Parity Games in Quasi-polynomial Time". SIAM Journal of Computing 51(2):152-188, 2020, Special Issue dedicated to ACM Symposium on Theory of Computation (STOC) 2017.
Committee: Virginia Vassilevska Williams (chair), Anuj Dawar, Fedor V. Fomin.
2020
Dániel Marx, Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, and Igor Razgon for the papers:
- Dániel Marx, "Parameterized graph separation problems", Theoretical Computer Science 351(3):394-406, 2006. Announced at International Workshop on Parameterized and Exact Computation (IWPEC) 2004;
- Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon, "A fixed-parameter algorithm for the directed feedback vertex set problem". Journal of the ACM 55(5):21:1-21:19, 2008. Announced at ACM Symposium on Theory of Computing (STOC) 2008.
Committee: Hans L. Bodlaender (chair), Anuj Dawar, Virginia Vassilevska Williams.
2019
Noga Alon, Raphael Yuster, and Uri Zwick for their paper:
- "Color-Coding", Journal of the ACM 42(4):844-856, 1995. Announced at ACM Symposium on Theory of Computing (STOC) 1994.
Committee: Jianer Chen (chair), Hans L. Bodlaender, Virginia Vassilevska Williams.
2018
Stefan Kratsch and Magnus Wahlström for their paper:
- "Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal", ACM Transactions on Algorithms 10(4):20:1-20:15, 2014. Announced at ACM Symposium on Theory of Computing (STOC) 2012.
Committee: Dániel Marx (chair), Jianer Chen, Hans L. Bodlaender.
2017
Fedor V. Fomin, Dieter Kratsch, and Fabrizio Grandoni for their paper:
- "A measure & conquer approach for the analysis of exact algorithms", Journal of the ACM 56(5):25:1-25:32, 2009. Announced at International Colloquium on Automata, Languages and Programming (ICALP) 2005 and ACM-SIAM Symposium on Discrete Algorithms (SODA) 2006.
Committee: David Eppstein (chair), Dániel Marx, Jianer Chen.
2016
Andreas Björklund for his paper:
- "Determinant Sums for Undirected Hamiltonicity", SIAM Journal of Computing 43(1):290-299, 2014. Announced at IEEE Symposium on Foundations of Computer Science (FOCS) 2010.
Committee: Jan Arne Telle (chair), David Eppstein, Dániel Marx.
2015
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, and Dimitrios M. Thilikos for their paper:
- "Subexponential Parameterized Algorithms on Bounded-Genus Graphs and H-Minor-Free Graphs", Journal of the ACM 52(6):866-893, 2005. Announced at ACM-SIAM Symposium on Discrete Algorithms (SODA) 2004.
Committee: Georg Gottlob (chair), Jan Arne Telle, David Eppstein.
2014
Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin, Lance Fortnow, and Rahul Santhanam for the papers:
- Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin, "On problems without polynomial kernels", Journal of Computer and System Sciences 75(8):423-434, 2009. Announced at International Colloquium on Automata, Languages and Programming (ICALP) 2008.
- Lance Fortnow, Rahul Santhanam, "Infeasibility of instance compression and succinct PCPs for NP", Journal of Computer and System Sciences 77(1):91-106, 2011. Announced at ACM Symposium on Theory of Computing (STOC) 2008.
Committee: Peter Widmayer (chair), Georg Gottlob, Jan Arne Telle.
2013
Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi, and Francis Zane for the papers:
- Chris Calabro, Russell Impagliazzo, Ramamohan Paturi, "On the Exact Complexity of Evaluating Quantified k-CNF", Algorithmica 65(4):817-827, 2013. Announced at International Symposium on Parameterized and Exact Computation (IPEC) 2010.
- Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi, "The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs", Journal of Computer and System Sciences 74(3):386-393, 2008. Announced at IEEE Conference on Computational Complexity (CCC) 2003.
- Russell Impagliazzo, Ramamohan Paturi, "On the Complexity of k-SAT", Journal of Computer and System Sciences 62(2):367-375, 2001.
- Russell Impagliazzo, Ramamohan Paturi, Francis Zane, "Which Problems Have Strongly Exponential Complexity?", Journal of Computer and System Sciences 63(4):512-530, 2001. Announced at IEEE Symposium on Foundations of Computer Science (FOCS) 1998.
Committee: Rolf Niedermeier (chair), Peter Widmayer, Georg Gottlob.