Nerode Prize: Difference between revisions
Content deleted Content added
m Bot: link syntax and minor changes |
m Added 2020 and 2021 recepients |
||
| Line 12: | Line 12: | ||
*2018: Stefan Kratsch and Magnus Wahlström for their work using [[matroid]] theory to develop polynomial-size kernels for [[odd cycle transversal]] and related problems.<ref>{{citation|url=http://algo2018.hiit.fi/speakers/#nerode|title=ALGO 2018 keynote speakers|publisher=Helsinki Institute for Information Technology|accessdate=2018-08-24}}</ref> |
*2018: Stefan Kratsch and Magnus Wahlström for their work using [[matroid]] theory to develop polynomial-size kernels for [[odd cycle transversal]] and related problems.<ref>{{citation|url=http://algo2018.hiit.fi/speakers/#nerode|title=ALGO 2018 keynote speakers|publisher=Helsinki Institute for Information Technology|accessdate=2018-08-24}}</ref> |
||
*2019: [[Noga Alon]], Raphael Yuster, and [[ Uri_Zwick|Uri Zwick]], for inventing [[Color-coding]] technique, a vastly important ingredient in the toolbox of parameterized algorithm design.<ref>{{citation|url=https://eatcs.org/index.php/component/content/article/1-news/2818-eatcs-ipec-nerode-prize-2019-|date=September 3, 2019|publisher=[[European Association for Theoretical Computer Science]]|title=EATCS-IPEC Nerode Prize 2019|accessdate=2020-01-01}}.</ref> |
*2019: [[Noga Alon]], Raphael Yuster, and [[ Uri_Zwick|Uri Zwick]], for inventing [[Color-coding]] technique, a vastly important ingredient in the toolbox of parameterized algorithm design.<ref>{{citation|url=https://eatcs.org/index.php/component/content/article/1-news/2818-eatcs-ipec-nerode-prize-2019-|date=September 3, 2019|publisher=[[European Association for Theoretical Computer Science]]|title=EATCS-IPEC Nerode Prize 2019|accessdate=2020-01-01}}.</ref> |
||
*2020: D. Marx, J. Chen, Y. Liu, S. Lu, B. O’Sullivan, I. Razgon, for inventing the concepts of separators and cuts which have become elegant and efficient tools used to establish the fixed parameter tractability of graph problems. |
|||
*2021: C. S. Calude, S. Jain, B. Khoussainov, W. Li, F. Stephan, for their [[quasipolynomial time algorithm]] for deciding [[parity games]]. |
|||
== See also == |
== See also == |
||
Revision as of 21:17, 11 September 2021
 |
The EATCS--IPEC 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 fixed-parameter tractable algorithms do not have polynomial-size 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 fixed-parameter-tractable 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 polynomial-size kernels for odd cycle transversal and related problems.[8]
- 2019: Noga Alon, Raphael Yuster, and Uri Zwick, for inventing Color-coding technique, a vastly important ingredient in the toolbox of parameterized algorithm design.[9]
- 2020: D. Marx, J. Chen, Y. Liu, S. Lu, B. O’Sullivan, I. Razgon, for inventing the concepts of separators and cuts which have become elegant and efficient tools used to establish the fixed parameter tractability of graph problems.
- 2021: C. S. Calude, S. Jain, B. Khoussainov, W. Li, F. Stephan, for their quasipolynomial time algorithm for deciding parity games.
See also
References
- ^ IPEC Nerode Prize, European Association for Theoretical Computer Science, retrieved 2015-09-03.
- ^ "EATCS-IPEC Nerode Prize", Parameterized Complexity, retrieved 2015-09-03.
- ^ EATCS-IPEC Nerode Prize 2013 - Laudatio, European Association for Theoretical Computer Science, retrieved 2015-09-03.
- ^ EATCS-IPEC Nerode Prize 2014 - Laudatio, European Association for Theoretical Computer Science, retrieved 2015-09-03.
- ^ Hajiaghayi Wins 2015 Nerode Prize, University of Maryland Institute for Advanced Computer Studies, May 8, 2015, retrieved 2015-09-03.
- ^ EATCS-IPEC Nerode Prize 2016, European Association for Theoretical Computer Science, August 29, 2016, retrieved 2016-08-29.
- ^ ALGO 2017, ALGO 2017, September 3, 2017, retrieved 2017-09-03.
- ^ ALGO 2018 keynote speakers, Helsinki Institute for Information Technology, retrieved 2018-08-24
- ^ EATCS-IPEC Nerode Prize 2019, European Association for Theoretical Computer Science, September 3, 2019, retrieved 2020-01-01.
 | This science awards article is a stub. You can help Wikipedia by expanding it. |