Gödel Prize
The Gödel Prize is an annual prize for outstanding papers in the area of
linear time.[1]
The Gödel Prize has been awarded since 1993. The prize is awarded alternately at ICALP (even years) and STOC (odd years). STOC is the ACM
North American conferences in theoretical computer science, whereas ICALP is the International Colloquium on Automata, Languages and Programming, one of the main European conferences in the field. To be eligible for the prize, a paper must be published in a refereed journal within the last 14 (formerly 7) years. The prize includes a reward of US$5000.[2]
The winner of the Prize is selected by a committee of six members. The EATCS President and the SIGACT Chair each appoint three members to the committee, to serve staggered three-year terms. The committee is chaired alternately by representatives of EATCS and SIGACT.
In contrast with the Gödel Prize, which recognizes outstanding papers, the Knuth Prize is awarded to individuals for their overall impact in the field.
Recipients
Year | Name(s) | Notes | Publication year |
---|---|---|---|
1993 | László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran, and Charles Rackoff | for the development of interactive proof systems | 1988,[paper 1] 1989[paper 2] |
1994 | Johan Håstad | for an exponential Boolean circuits (for the parity function ). |
1989[paper 3] |
1995 | Neil Immerman and Róbert Szelepcsényi | for the Immerman–Szelepcsényi theorem regarding nondeterministic space complexity | 1988,[paper 4] 1988[paper 5] |
1996 | Mark Jerrum and Alistair Sinclair | for work on Markov chains and the approximation of the permanent of a matrix |
1989,[paper 6] 1989[paper 7] |
1997 | Joseph Halpern and Yoram Moses | for defining a formal notion of "knowledge" in distributed environments | 1990[paper 8] |
1998 | Seinosuke Toda | for Toda's theorem, which showed a connection between counting solutions (PP) and alternation of quantifiers (PH) | 1991[paper 9] |
1999 | Peter Shor | for quantum computer |
1997[paper 10] |
2000 | Moshe Y. Vardi and Pierre Wolper |
for work on finite automata |
1994[paper 11] |
2001 | Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, and Mario Szegedy | for the PCP theorem and its applications to hardness of approximation | 1996,[paper 12] 1998,[paper 13] 1998[paper 14] |
2002 | Géraud Sénizergues | for proving that equivalence of deterministic pushdown automata is decidable | 2001[paper 15] |
2003 | Yoav Freund and Robert Schapire | for the AdaBoost algorithm in machine learning | 1997[paper 16] |
2004 | Maurice Herlihy, Michael Saks, Nir Shavit and Fotios Zaharoglou | for applications of topology to the theory of distributed computing | 1999,[paper 17] 2000[paper 18] |
2005 | Noga Alon, Yossi Matias and Mario Szegedy | for their foundational contribution to streaming algorithms | 1999[paper 19] |
2006 | Manindra Agrawal, Neeraj Kayal, Nitin Saxena | for the AKS primality test | 2004[paper 20] |
2007 | Alexander Razborov, Steven Rudich | for natural proofs | 1997[paper 21] |
2008 | Shang-Hua Teng |
for smoothed analysis of algorithms | 2004[paper 22] |
2009 | Omer Reingold, Salil Vadhan, Avi Wigderson | for log space |
2002,[paper 23] 2008[paper 24] |
2010 | Sanjeev Arora, Joseph S. B. Mitchell | for their concurrent discovery of a Travelling Salesman Problem (ETSP) |
1998,[paper 25]
1999[paper 26] |
2011 | Johan Håstad | for proving optimal inapproximability results for various combinatorial problems | 2001[paper 27] |
2012 | Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden and Éva Tardos | for laying the foundations of algorithmic game theory[3] | 2009,[paper 28] 2002,[paper 29] 2001[paper 30] |
2013 | Dan Boneh, Matthew K. Franklin, and Antoine Joux | for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography[4] | 2003,[paper 31]
2004[paper 32] |
2014 | Ronald Fagin, Amnon Lotem , and Moni Naor | for Optimal Aggregation Algorithms for middleware[5] | 2003,[paper 33] |
2015 | Shang-Hua Teng
|
for their series of papers on nearly-linear-time Laplacian solvers[6] |
2011[paper 34] 2013[paper 35] 2014[paper 36] |
2016 | Stephen Brookes and Peter W. O'Hearn | for their invention of Concurrent Separation Logic | 2007,[paper 37] 2007[paper 38] |
2017[2] | Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith | for the invention of differential privacy | 2006[paper 39] |
2018[7] | Oded Regev
|
for introducing the learning with errors problem | 2009[paper 40] |
2019[8] | Irit Dinur | for her new proof of the PCP theorem by gap amplification | 2007[paper 41] |
2020[9] | Robin Moser and Gábor Tardos | for their constructive proof of the Lovász local lemma | 2010[paper 42] |
2021[10] | Andrei Bulatov, Jin-Yi Cai, Xi Chen, Martin Dyer, and David Richerby | for their work on the classification of the counting complexity of constraint satisfaction problems | 2013[paper 43]
2013[paper 44] 2017[paper 45] |
2022[11] | Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan | for their transformative contributions to cryptography by constructing efficient fully homomorphic encryption (FHE) schemes | 2014,[paper 46] 2014[paper 47] |
2023[12] | Samuel Fiorini, Serge Massar, and Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf, and Thomas Rothvoss | for showing that any extended formulation for the TSP polytope has exponential size | 2015,[paper 48] 2017[paper 49] |
Winning papers
- ISSN 0022-0000
- ISSN 1095-7111
- ISBN 978-0-89232-896-3, archived from the original(PDF) on 2012-02-22
- ISSN 1095-7111
- S2CID 10838178
- ISSN 0890-5401
- ISSN 1095-7111
- S2CID 52151232
- ISSN 1095-7111
- S2CID 2337707
- ISSN 0890-5401, archived from the original(PDF) on 2011-08-25
- ISSN 0004-5411
- S2CID 751563, archived from the original(PDF) on 2011-06-10
- S2CID 8561542, archived from the original(PDF) on 2011-06-10
- ISSN 0304-3975
- ISSN 1090-2724
- S2CID 5797174. Gödel prize lecture
- doi:10.1006/jcss.1997.1545. First presented at the Symposium on Theory of Computing(STOC) in 1996.
- ISSN 0003-486X
- ISSN 0004-5411
- S2CID 120739405
- S2CID 207168478[permanent dead link]
- S2CID 3023351
- ISSN 1095-7111
- S2CID 5120748
- .
- S2CID 207638789.
- .
- MR 2001745.
- S2CID 3350730.
- .
- S2CID 9646279.
- S2CID 9151077.
- S2CID 1750944.
- .
- .
- ISBN 978-3-540-32731-8.
- S2CID 207156623.
- S2CID 53244523.
- ISSN 0004-5411.
- S2CID 8964233.
- S2CID 1247279.
- S2CID 1053684.
- S2CID 8831240.
- S2CID 2602543.
- ^
Fiorini, Samuel; Massar, Serge; Pokutta, Sebastian; Tiwary, Hans Raj; de Wolf, Ronald (2015). "Exponential Lower Bounds for Polytopes in Combinatorial Optimization". Journal of the ACM. 62 (2): 17:1–17:23. S2CID 7372000.
- ^
Rothvoss, Thomas (2017). "The Matching Polytope has Exponential Extension Complexity". Journal of the ACM. 64 (6): 41:1–41:19. S2CID 47045361.
See also
Notes
- ^ "The Gödel Letter". 2009-02-12.
- ^ a b "2017 Gödel Prize". European Association for Theoretical Computer Science. EATCS. Retrieved 29 March 2017.
- ^ "Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory". 16 May 2012. Archived from the original on 18 July 2013. Retrieved 16 May 2012.
- ^ ACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security Archived 2013-06-01 at the Wayback Machine, Association for Computing Machinery, May 29, 2013.
- ^ Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources, Association for Computing Machinery, April 30, 2014.
- ^ 2015 Gödel Prize announcement Archived 2017-12-09 at the Wayback Machine by Association for Computing Machinery.
- ^ "2018 Gödel Prize citation".
- ^ "2019 Gödel Prize citation".
- ^ "2020 Gödel Prize citation".
- ^ "2021 Gödel Prize citation".
- ^ "2022 Gödel Prize citation".
- ^ "2023 Gödel Prize citation".