The EATCS-IPEC Nerode Prize for outstanding papers in multivariate algorithmics
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).
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.
In 2016, the winner was Andreas Björklund for the paper:
- "Determinant Sums for Undirected Hamiltonicity", SIAM Journal of Computing, 2014
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
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
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
The winning paper is selected by a committee of three members. The committee for 2017 consists of the following three people.
Jianer Chen (Texas A&M) ude.umat.sc|nehc#ude.umat.sc|nehc
Daniel Marx (Hungarian Academy of Sciences) uh.emb.sc|xramd#uh.emb.sc|xramd
David Eppstein (UC Irvine), ude.icu.sci|nietsppe#ude.icu.sci|nietsppe (chair)
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.
Previous committee members are Rolf Niedermeier (2013), Peter Widmayer (2013-14), Georg Gottlob (2013-15), Jan Arne Telle (2014-16).
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 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 deadline for nominations for the award in 2016 was February 15