Jump to content

Nerode Prize: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
Winners: added secondary sources
m v2.05 - Autofix / Fix errors for CW project (Link equal to linktext)
 
(7 intermediate revisions by 6 users not shown)
Line 5: Line 5:
The prize winners so far have been:
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]].<ref>{{citation|url=http://www.eatcs.org/index.php/component/content/article/20-eatcs-awards/1596-eatcs-ipec-nerode-prize-2013-laudatio|title=EATCS-IPEC Nerode Prize 2013 - Laudatio|publisher=[[European Association for Theoretical Computer Science]]|accessdate=2015-09-03}}.</ref>
*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]].<ref>{{citation|url=http://www.eatcs.org/index.php/component/content/article/20-eatcs-awards/1596-eatcs-ipec-nerode-prize-2013-laudatio|title=EATCS-IPEC Nerode Prize 2013 - Laudatio|publisher=[[European Association for Theoretical Computer Science]]|accessdate=2015-09-03}}.</ref>
*2014: [[Hans L. Bodlaender]], [[Rod Downey|Rodney G. Downey]], [[Michael Fellows|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.<ref>{{Cite web |last=Nelson |first=Patrick |date=October 6, 2014 |title=Academic wins international maths prize |url=https://www.cdu.edu.au/enews/stories/fellows |url-status=live |access-date=November 1, 2022}}</ref><ref>{{citation|url=https://www.eatcs.org/index.php/component/content/article/20-eatcs-awards/1874-eatcs-ipec-nerode-prize-2014-laudatio|title=EATCS-IPEC Nerode Prize 2014 - Laudatio|publisher=[[European Association for Theoretical Computer Science]]|accessdate=2015-09-03}}.</ref>
*2014: [[Hans L. Bodlaender]], [[Rod Downey|Rodney G. Downey]], [[Michael Fellows|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.<ref>{{Cite web |last=Nelson |first=Patrick |date=October 6, 2014 |title=Academic wins international maths prize |url=https://www.cdu.edu.au/enews/stories/fellows |access-date=November 1, 2022}}</ref><ref>{{citation|url=https://www.eatcs.org/index.php/component/content/article/20-eatcs-awards/1874-eatcs-ipec-nerode-prize-2014-laudatio|title=EATCS-IPEC Nerode Prize 2014 - Laudatio|publisher=[[European Association for Theoretical Computer Science]]|accessdate=2015-09-03}}.</ref>
*2015: [[Erik Demaine]], [[Fedor_Fomin|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.<ref>{{citation|url=http://www.umiacs.umd.edu/about-us/news/hajiaghayi-wins-2015-nerode-prize|title=Hajiaghayi Wins 2015 Nerode Prize|date=May 8, 2015|publisher=University of Maryland Institute for Advanced Computer Studies|accessdate=2015-09-03}}.</ref>
*2015: [[Erik Demaine]], [[Fedor_Fomin|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.<ref>{{citation|url=http://www.umiacs.umd.edu/about-us/news/hajiaghayi-wins-2015-nerode-prize|title=Hajiaghayi Wins 2015 Nerode Prize|date=May 8, 2015|publisher=University of Maryland Institute for Advanced Computer Studies|accessdate=2015-09-03}}.</ref>
* 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 [[Hamiltonian_path_problem|finding Hamiltonian cycles]]<ref>{{citation|url=http://eatcs.org/index.php/component/content/article/1-news/2333-eatcs-ipec-nerode-prize-2016|title=EATCS-IPEC Nerode Prize 2016
* 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 [[Hamiltonian_path_problem|finding Hamiltonian cycles]]<ref>{{citation|url=http://eatcs.org/index.php/component/content/article/1-news/2333-eatcs-ipec-nerode-prize-2016|title=EATCS-IPEC Nerode Prize 2016
Line 11: Line 11:
*2017: [[Fedor_Fomin|Fedor V. Fomin]], Fabrizio Grandoni, and Dieter Kratsch, for developing the "measure and conquer" method for the analysis of backtracking algorithms.<ref>{{citation|url=https://algo2017.ac.tuwien.ac.at/awards/|title=ALGO 2017|date=September 3, 2017|publisher=ALGO 2017|accessdate=2017-09-03}}.</ref>
*2017: [[Fedor_Fomin|Fedor V. Fomin]], Fabrizio Grandoni, and Dieter Kratsch, for developing the "measure and conquer" method for the analysis of backtracking algorithms.<ref>{{citation|url=https://algo2017.ac.tuwien.ac.at/awards/|title=ALGO 2017|date=September 3, 2017|publisher=ALGO 2017|accessdate=2017-09-03}}.</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>{{Cite web |date=May 13, 2018 |title=Magnus Wahlström was awarded the 2018 Nerode Prize |url=https://www.royalholloway.ac.uk/research-and-teaching/departments-and-schools/computer-science/news/magnus-wahlstroem-awarded-the-2018-nerode-prize/ |url-status=live |archive-url=https://web.archive.org/web/20220125011724/https://www.royalholloway.ac.uk/research-and-teaching/departments-and-schools/computer-science/news/magnus-wahlstroem-awarded-the-2018-nerode-prize/ |archive-date=January 25, 2022 |access-date=November 1, 2022}}</ref><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>{{Cite web |date=May 13, 2018 |title=Magnus Wahlström was awarded the 2018 Nerode Prize |url=https://www.royalholloway.ac.uk/research-and-teaching/departments-and-schools/computer-science/news/magnus-wahlstroem-awarded-the-2018-nerode-prize/ |url-status=live |archive-url=https://web.archive.org/web/20220125011724/https://www.royalholloway.ac.uk/research-and-teaching/departments-and-schools/computer-science/news/magnus-wahlstroem-awarded-the-2018-nerode-prize/ |archive-date=January 25, 2022 |access-date=November 1, 2022}}</ref><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 the [[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]], for inventing the [[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.<ref>{{Cite web |last=Darmody |first=Jenny |date=2020-12-16 |title=Ireland’s Prof Barry O’Sullivan wins global computer science award |url=https://www.siliconrepublic.com/innovation/barry-o-sullivan-nerode-prize |access-date=2022-11-01 |website=Silicon Republic |language=en}}</ref>
*2020: Daniel Marx, Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, Igor Razgon, for inventing the concepts of important separators and cuts which have become elegant and efficient tools used to establish the fixed parameter tractability of graph problems.<ref>{{Cite web |last=Darmody |first=Jenny |date=2020-12-16 |title=Ireland's Prof Barry O'Sullivan wins global computer science award |url=https://www.siliconrepublic.com/innovation/barry-o-sullivan-nerode-prize |access-date=2022-11-01 |website=Silicon Republic |language=en}}</ref>
*2021: C. S. Calude, S. Jain, B. Khoussainov, W. Li, F. Stephan, for their [[quasipolynomial time algorithm]] for deciding [[parity games]].<ref>{{Cite web |title=NUS Computing professors Sanjay Jain and Frank Stephan win EATCS-IPEC Nerode Prize |url=https://www.comp.nus.edu.sg/news/2021-sanjay-frank-eatcs-ipec |access-date=2022-11-01 |website=NUS Computing |language=en-gb}}</ref>
*2021: C. S. Calude, S. Jain, B. Khoussainov, W. Li, F. Stephan, for their [[Quasi-polynomial time|quasipolynomial time]] algorithm for deciding [[parity games]].<ref>{{Cite web |title=NUS Computing professors Sanjay Jain and Frank Stephan win EATCS-IPEC Nerode Prize |url=https://www.comp.nus.edu.sg/news/2021-sanjay-frank-eatcs-ipec |access-date=2022-11-01 |website=NUS Computing |language=en-gb}}</ref>
*2022: B. Courcelle for his work on the definability of graph properties in [[monadic second-order logic]].
*2022: [[Bruno Courcelle]] for [[Courcelle's theorem]] on the fixed-parameter tractability of graph properties in [[monadic second-order logic]].
*2023: Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk for their paper ''Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time''.<ref>{{citation|url=https://eatcs.org/index.php/component/content/article/1-news/2949-eatcs-ipec-nerode-prize-2023|title=EATCS-IPEC Nerode Prize 2023|publisher=[[European Association for Theoretical Computer Science]]|accessdate=2024-01-18}}.</ref>
*2024: Hans L. Bodlaender, [[Fedor_Fomin|Fedor V. Fomin]], Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos for their paper ''(Meta) Kernelization''.<ref>{{citation|url=https://eatcs.org/index.php/component/content/article/1-news/2987-eatcs-ipec-nerode-prize-2024|title=EATCS-IPEC Nerode Prize 2024|publisher=[[European Association for Theoretical Computer Science]]|accessdate=2024-09-06}}.</ref>


== See also ==
== See also ==

Latest revision as of 21:35, 14 December 2024

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

[edit]

The prize winners so far have been:

See also

[edit]

References

[edit]
  1. ^ IPEC Nerode Prize, European Association for Theoretical Computer Science, retrieved 2015-09-03.
  2. ^ "EATCS-IPEC Nerode Prize", Parameterized Complexity, retrieved 2015-09-03.
  3. ^ EATCS-IPEC Nerode Prize 2013 - Laudatio, European Association for Theoretical Computer Science, retrieved 2015-09-03.
  4. ^ Nelson, Patrick (October 6, 2014). "Academic wins international maths prize". Retrieved November 1, 2022.
  5. ^ EATCS-IPEC Nerode Prize 2014 - Laudatio, European Association for Theoretical Computer Science, retrieved 2015-09-03.
  6. ^ Hajiaghayi Wins 2015 Nerode Prize, University of Maryland Institute for Advanced Computer Studies, May 8, 2015, retrieved 2015-09-03.
  7. ^ EATCS-IPEC Nerode Prize 2016, European Association for Theoretical Computer Science, August 29, 2016, retrieved 2016-08-29.
  8. ^ ALGO 2017, ALGO 2017, September 3, 2017, retrieved 2017-09-03.
  9. ^ "Magnus Wahlström was awarded the 2018 Nerode Prize". May 13, 2018. Archived from the original on January 25, 2022. Retrieved November 1, 2022.
  10. ^ ALGO 2018 keynote speakers, Helsinki Institute for Information Technology, retrieved 2018-08-24
  11. ^ EATCS-IPEC Nerode Prize 2019, European Association for Theoretical Computer Science, September 3, 2019, retrieved 2020-01-01.
  12. ^ Darmody, Jenny (2020-12-16). "Ireland's Prof Barry O'Sullivan wins global computer science award". Silicon Republic. Retrieved 2022-11-01.
  13. ^ "NUS Computing professors Sanjay Jain and Frank Stephan win EATCS-IPEC Nerode Prize". NUS Computing. Retrieved 2022-11-01.
  14. ^ EATCS-IPEC Nerode Prize 2023, European Association for Theoretical Computer Science, retrieved 2024-01-18.
  15. ^ EATCS-IPEC Nerode Prize 2024, European Association for Theoretical Computer Science, retrieved 2024-09-06.