Nerode Prize
Jump to navigation
Jump to search
This content was retrieved from
Wikipedia : http://en.wikipedia.org/wiki/Nerode_PrizeThis article relies too much on references to primary sources. (May 2013) (Learn how and when to remove this template message)

The EATCSIPEC Nerode Prize is a theoretical computer science prize awarded for outstanding research in the area of multivariate algorithmics. It is awarded by the European Association for Theoretical Computer Science and the International Symposium on Parameterized and Exact Computation.^{[1]} The prize was offered for the first time in 2013.^{[2]}
Winners
The prize winners so far have been:
 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.^{[3]}
 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 fixedparameter tractable algorithms do not have polynomialsize kernels unless the polynomial hierarchy collapses.^{[4]}
 2015: Erik Demaine, Fedor V. Fomin, Mohammad Hajiaghayi, and Dimitrios Thilikos, for their research on bidimensionality, defining a broad framework for the design of fixedparametertractable algorithms for domination and covering problems on graphs.^{[5]}
 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 ^{[6]}
 2017: Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch, for developing the "measure and conquer" method for the analysis of backtracking algorithms.^{[7]}
 2018: Stefan Kratsch and Magnus Wahlström for their work using matroid theory to develop polynomialsize kernels for odd cycle transversal and related problems.^{[8]}
References
 ^ IPEC Nerode Prize, European Association for Theoretical Computer Science, retrieved 20150903.
 ^ "EATCSIPEC Nerode Prize", Parameterized Complexity, retrieved 20150903.
 ^ EATCSIPEC Nerode Prize 2013  Laudatio, European Association for Theoretical Computer Science, retrieved 20150903.
 ^ EATCSIPEC Nerode Prize 2014  Laudatio, European Association for Theoretical Computer Science, retrieved 20150903.
 ^ Hajiaghayi Wins 2015 Nerode Prize, University of Maryland Institute for Advanced Computer Studies, May 8, 2015, retrieved 20150903.
 ^ EATCSIPEC Nerode Prize 2016, European Association for Theoretical Computer Science, August 29, 2016, retrieved 20160829.
 ^ ALGO 2017, ALGO 2017, September 3, 2017, retrieved 20170903.
 ^ ALGO 2018 keynote speakers, Helsinki Institute for Information Technology, retrieved 20180824
P ≟ NP  This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it. 
This awardrelated article is a stub. You can help Wikipedia by expanding it. 
This page is based on the copyrighted Wikipedia article "Nerode Prize"; it is used under the Creative Commons
AttributionShareAlike 3.0 Unported License (CCBYSA). You may
redistribute it, verbatim or modified, providing that you comply with
the terms of the CCBYSA