Jump to content

Nerode Prize: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
ParAlg (talk | contribs)
No edit summary
ParAlg (talk | contribs)
No edit summary
Line 6: Line 6:
*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>{{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>{{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 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
|date=August 29, 2016|publisher=[[European Association for Theoretical Computer Science]]|accessdate=2016-08-29}}.</ref>
|date=August 29, 2016|publisher=[[European Association for Theoretical Computer Science]]|accessdate=2016-08-29}}.</ref>

Revision as of 16:33, 1 June 2017

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:

References

  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. ^ EATCS-IPEC Nerode Prize 2014 - Laudatio, European Association for Theoretical Computer Science, retrieved 2015-09-03.
  5. ^ Hajiaghayi Wins 2015 Nerode Prize, University of Maryland Institute for Advanced Computer Studies, May 8, 2015, retrieved 2015-09-03.
  6. ^ EATCS-IPEC Nerode Prize 2016, European Association for Theoretical Computer Science, August 29, 2016, retrieved 2016-08-29.