The EATCS-IPEC Nerode Prize for outstanding papers in multivariate algorithmics
**2022 CALL FOR NOMINATIONS FOR THE EATCS-IPEC NERODE PRIZE
Nomination Deadline: 15 May, 2022**
Decision: 1 July, 2022.
The EATCS-IPEC Nerode Prize for outstanding papers in the area of multivariate algorithmics, is presented annually with the presentation taking place at IPEC (International Symposium on Parameterized and Exact Computation). IPEC 2022 is due to take place as part of ALGO 2022 on 5-9 September in Potsdam, Germany. 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.
The EATCS-IPEC Nerode Prize is an award for outstanding papers in multivariate algorithmics. The award is presented annually with the presentation taking place at IPEC (International Symposium on Parameterized and Exact Computation), which often is co-located with ALGO. The award winners are invited to give a presentation.
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.
Eligibility
The Nerode Prize is an annual prize for outstanding work in multivariate algorithmics and parameterized complexity, published in a recognized refereed journal by an individual or a team of authors.
Any research paper or series of research papers by a single author or by a team of authors published in a recognized refereed journal. The year of publication should be at least two years and at most ten years before the year of the award nomination. 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.
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.
Nominations should contain a brief summary of the technical content of the nominated paper and a brief explanation of its significance. Send copies to the members of the committee. The Subject line of the nomination E-mail should contain the group of words "Nerode Prize Nomination". Note that eligibility rules have changed. Past rules requiring a number of years before/after the publication of the nominated paper have been deleted.
Committee
The Award Committee is responsible for updating this PC Wiki .
The Award Committee should coordinate with the Program Committee Chairs and the PC Publicity Chair (Frances Rosamond) with the names and email addresses of the winners, the announcement date (when the winners are informed), the Laudatio, and any other ceremony.
The Nerode committee rotates, with each member in the committee for three years.
Award Committee 2022
The winning paper(s) will be selected by the EATCS-IPEC Nerode Prize Award Committee. This 2022 committee consists of the following people.
Anuj Dawar, chair (University of Cambridge, ku.ca.mac.lc|rawad.juna#ku.ca.mac.lc|rawad.juna)
Fedor Fomin (University of Bergen, on.biu|nimof.rodef#on.biu|nimof.rodef)
Thore Husfeldt (IT University of Copenhagen, kd.uti|eroht#kd.uti|eroht)
Winners
Laudations for all winners can be found on the website https://eatcs.org/index.php/nerode-prize
- 2021. In 2021, the winning paper was by Cristian Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Frank Stephan,
"Deciding Parity Games in Quasi-polynomial Time”. SIAM Journal of Computing, Special Issue dedicated to STOC 2017, pp. 152-188, published January 2020.
Committee: Virginia V. Williams, Anuj Dawar, Fedor Fomin
- 2020. In 2020, there were two winning papers. These were by Marx, D., Chen, J., Liu, Y., Lu, S., O’Sullivan, B., Razgon, I.
Marx, D.: "Parameterized graph separation problems". Theoretical Computer Science 351(3), 394–406 (2006)
Chen, J., Liu, Y., Lu, S., O’Sullivan, B., Razgon, I.: "A fixed-parameter algorithm for the directed feedback vertex set problem". J. ACM 55(5) (2008)
Committee: Hans L. Bodlaender, Anuj Dawar, Virgi V. Williams
- 2019. In 2019, the winners were Noga Alon, Raphael Yuster, and Uri Zwick for their paper:
"Color-Coding". Journal of the Association for Computing Machinery, Vol 42, No 4, pp. 844-856 (1995).
Committee: Jianer Chen, Hans L. Bodlaender, Virgi V. Williams
- 2018. The 2018 winners were Stefan Kratsch and Magnus Wahlström for their paper:
"Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal." ACM Trans. Algorithms 10(4): 20:1-20:15 (2014)
Committee: Daniel Marx, Jianer Chen, Hans L. Bodlaender
- 2017. In 2017, the winners were Fedor V. Fomin, Dieter Kratsch, Fabrizio Grandoni for the paper:
"A measure & conquer approach for the analysis of exact algorithms", Journal of the ACM, 2009
Committee: David Eppstein, Daniel Marx, Jianer Chen
- 2016. In 2016, the winner was Andreas Björklund for the paper:
- "Determinant Sums for Undirected Hamiltonicity", SIAM Journal of Computing, 2014
Committee: David Eppstein, Daniel Marx, Jan Arne Telle
- 2015. In 2015, the winners were Eric D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
for the paper:
- "Subexponential Parameterized Algorithms on Bounded-Genus Graphs and H-Minor-Free Graphs", Journal of the ACM, 2005
Committee: David Eppstein, Jan Arne Telle, and Georg Gottlob (chair)
- 2014. In 2014, the winners were Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin, Lance Fortnow, Rahul Santhanam for the papers:
- "On problems without polynomial kernels", Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin, Journal of Computer and System Sciences, 2009
- "Infeasibility of instance compression and succinct PCPs for NP", Lance Fortnow, Rahul Santhanam, Journal of Computer and System Sciences, 2011
Committee: Georg Gottlob, Jan Arne Telle, and Peter Widmayer (chair)
- 2013. In 2013, the prize was awarded for the first time. Winners were Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi, Francis Zane for the papers:
- "On the Exact Complexity of Evaluating Quantified k-CNF", Algorithmica 2013,
- "The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs", Journal of Computer and System Sciences 2008
- "On the Complexity of k-SAT", Journal of Computer and System Sciences 2001
- "Which Problems Have Strongly Exponential Complexity?", Journal of Computer and System Sciences 2001
Committee: Georg Gottlob, Rolf Niedermeier (chair), and Peter Widmayer