IPEC Nerode Prize

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). 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.

IPEC 2024 will take place as part of ALGO 2024 on 4–6 September 2024 at Royal Holloway, United Kingdom.

The prize was awarded for the first time in 2013.

Award Committee

The winning paper(s) is selected by a committee of three members.

This year's committee consists of:

  • Thore Husfeldt, chair (IT University of Copenhagen,  This e-mail address is being protected from spambots. You need JavaScript enabled to view it )
  • Sang-il Oum (IBS and KAIST,  This e-mail address is being protected from spambots. You need JavaScript enabled to view it )
  • Russell Impagliazzo (UC San Diego,  This e-mail address is being protected from spambots. You need JavaScript enabled to view it )

Deadline for Nominations: Monday, 29 April, 2024, anywhere on Earth

Decision, expected: 15 June, 2024.

The Award Committee is solely responsible for the selection of the winner of the award which may be shared by more than one paper or series of papers. The Award Committee reserves the right to declare no winner at all.

Eligibility

The Nerode Prize is given to a research paper or series of research papers by a single author or by a team of authors published in a recognized refereed journal. The research work nominated for the award should be in the area of multivariate algorithms and complexity meant in a broad sense, which 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.

Note that the past restrictions that required a certain number of years before/after the publication of the nominated papers have 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. The Subject line of the nomination e-mail should contain the phrase "Nerode Prize Nomination".

A brief history of the prize follows below.

2024 / Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos

Place: IPEC (United Kingdom)

  • "(Meta) Kernelization." J. ACM 63(5): 44:1-44:69 (2016), announced at Foundations of Computer Science (FOCS) 2010.

Committee: 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

Place: IPEC (Amsterdam)

  • "Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time." ACM Trans. Algorithms 18(2): 17:1-17:31 (2022). Conference version: FOCS 2011

Committee: Fedor Fomin, Thore Husfeldt, Sang-il Oum

2022 / Bruno Courcelle

Place: IPEC (Postdam)

  • "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, Fedor Fomin, Thore Husfeldt

2021 / Cristian Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Frank Stephan

Place: IPEC (Lisbon)

  • "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 / Marx, D., Chen, J., Liu, Y., Lu, S., O’Sullivan, B., Razgon, I.

Place: IPEC (Hong Kong)

  • 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

Laudation

2019 / Noga Alon, Raphael Yuster, and Uri Zwick

Place: IPEC (Munich)

  • "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

Laudation

2018 / Stefan Kratsch, Magnus Wahlström

Place: IPEC (Helsinki)

  • "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

Laudation

2017 / Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch

Place: IPEC (Vienna)

  • "A Measure & Conquer Approach for the Analysis of Exact Algorithms" Journal of the ACM 65 (5): Article 25, 2009.

Committee: David Eppstein, Daniel Marx, Jianer Chen

Laudation

2016 / Andreas Björklund

Place: IPEC (Aarhus)

  • "Determinant Sums for Undirected Hamiltonicity", SIAM Journal of Computing 43(1): 280–299 (2014)

Committee: David Eppstein, Daniel Marx, Jan Arne Telle

Laudation

2015 / Eric D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos

Place: IPEC (Patras)

Committee: David Eppstein, Jan Arne Telle, and Georg Gottlob (chair)

Laudation

2014 / Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin, Lance Fortnow, Rahul Santhanam

Place: IPEC (Wrocław)

Committee: Georg Gottlob, Jan Arne Telle, and Peter Widmayer (chair)

Laudation

2013 / Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi, Francis Zane

Place: IPEC (Sophia Antipolis)

Committee: Georg Gottlob, Rolf Niedermeier (chair), and Peter Widmayer

Laudation

e-max.it: your social media marketing partner
 
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.