Gödel Prize Explained

The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory (ACM SIGACT). The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or 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 Symposium on Theory of Computing, one of the main 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.

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

Yearwidth=40% class="unsortable"Name(s)width=45% class="unsortable"NotesPublication year
1993 for the development of interactive proof systems 1988, 1989
1994 for an exponential lower bound on the size of constant-depth Boolean circuits (for the parity function). 1989
1995 for the Immerman–Szelepcsényi theorem regarding nondeterministic space complexity 1988, 1988
1996 1989, 1989
1997 for defining a formal notion of "knowledge" in distributed environments 1990
1998 for Toda's theorem, which showed a connection between counting solutions (PP) and alternation of quantifiers (PH) 1991
1999 1997
2000 1994
2001 for the PCP theorem and its applications to hardness of approximation 1996, 1998, 1998
2002 2001
2003 1997
2004 1999,[2] 2000
2005 for their foundational contribution to streaming algorithms 1999[3]
2006 2004
2007 for natural proofs 1997
2008 Daniel Spielman, Shang-Hua Tengfor smoothed analysis of algorithms 2004
2009 2002, 2008
2010 Sanjeev Arora, Joseph S. B. Mitchell1998, 1999
2011 for proving optimal inapproximability results for various combinatorial problems 2001
2012 for laying the foundations of algorithmic game theory[4] 2009,[5] 2002,[6] 2001[7]
2013 for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography[8] 2003,[9] 2004[10]
2014 for Optimal Aggregation Algorithms for middleware[11] 2003,[12]
2015 for their series of papers on nearly-linear-time Laplacian solvers[13] 2011[14] 2013[15] 2014[16]
2016Stephen Brookes and Peter W. O'Hearnfor their invention of Concurrent Separation Logic2007,[17] 2007[18]
2017[19] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smithfor the invention of differential privacy2006[20]
2018[21] Oded Regevfor introducing the learning with errors problem2009[22]
2019[23] Irit Dinurfor her new proof of the PCP theorem by gap amplification2007[24]
2020[25] Robin Moser and Gábor Tardosfor their constructive proof of the Lovász local lemma2010[26]
2021[27] Andrei Bulatov, Jin-Yi Cai, Xi Chen, Martin Dyer, and David Richerbyfor their work on the classification of the counting complexity of constraint satisfaction problems2013[28] 2013[29] 2017[30]
2022[31] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathanfor their transformative contributions to cryptography by constructing efficient fully homomorphic encryption (FHE) schemes2014,[32] 2014[33]
2023[34] Samuel Fiorini, Serge Massar, and Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf, and Thomas Rothvossfor showing that any extended formulation for the TSP polytope has exponential size2015,[35] 2017[36]
2024[37] Ryan Williamsfor his work on circuit lower bounds and the “algorithms to lower bounds” paradigm2011[38]

See also

References

Notes and References

  1. Web site: The Gödel Letter. 2009-02-12.
  2. . Gödel prize lecture
  3. . First presented at the Symposium on Theory of Computing (STOC) in 1996.
  4. News: Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory. 16 May 2012. 16 May 2012. dead. https://web.archive.org/web/20130718154540/http://www.acm.org/press-room/news-releases/2012/goedel-prize-2012. 18 July 2013.
  5. Koutsoupias. Elias. Papadimitriou, Christos. Worst-case equilibria. Computer Science Review. 2009. 3. 2. 65–69. 10.1016/j.cosrev.2009.04.003.
  6. Roughgarden. Tim. Tardos, Éva. How bad is selfish routing?. Journal of the ACM. 2002. 49. 2. 236–259. 10.1145/506147.506153. 10.1.1.147.1081. 207638789.
  7. Nisan. Noam. Ronen, Amir. Algorithmic Mechanism Design. Games and Economic Behavior. 2001. 35. 1–2. 166–196. 10.1006/game.1999.0790. 10.1.1.21.1731.
  8. http://www.acm.org/press-room/news-releases/2013/goedel-prize-13/ ACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security
  9. Boneh . Dan . Franklin . Matthew . 10.1137/S0097539701398521 . 3 . SIAM Journal on Computing . 2001745 . 586–615 . Identity-based encryption from the Weil pairing . 32 . 2003. 10.1.1.66.1131 .
  10. Joux . Antoine . 10.1007/s00145-004-0312-y . 4 . Journal of Cryptology . 2090557 . 263–276 . A one round protocol for tripartite Diffie-Hellman . 17 . 2004. 3350730 . free .
  11. https://eatcs.org/index.php/component/content/article/1-news/1908-goedel-prize-2014 Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources
  12. Fagin . Ronald . Lotem . Amnon . Naor . Moni . 10.1016/S0022-0000(03)00026-6 . 4 . Journal of Computer and System Sciences . 614–656 . Optimal aggregation algorithms for middleware . 66 . 2003. cs/0204046 .
  13. http://www.sigact.org/Prizes/Godel/citation2015.pdf 2015 Gödel Prize announcement
  14. Spielman. Daniel A.. Teng. Shang-Hua. Spectral Sparsification of Graphs. SIAM Journal on Computing. 40. 4. 2011. 981–1025. 0097-5397. 10.1137/08074489X. 0808.4134. 9646279.
  15. Spielman. Daniel A.. Teng. Shang-Hua. A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning. SIAM Journal on Computing. 42. 1. 2013. 1–26. 0097-5397. 10.1137/080744888. 0809.3232. 9151077.
  16. Spielman. Daniel A.. Teng. Shang-Hua. Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems. SIAM Journal on Matrix Analysis and Applications. 35. 3. 2014. 835–885. 0895-4798. 10.1137/090771430. cs/0607105. 1750944.
  17. Brookes. Stephen. A Semantics for Concurrent Separation Logic. Theoretical Computer Science. 2007. 375. 1–3. 227–270. 10.1016/j.tcs.2006.12.034.
  18. O'Hearn. Peter. Resources, Concurrency and Local Reasoning. Theoretical Computer Science. 2007. 375. 1–3. 271–307. 10.1016/j.tcs.2006.12.035. free.
  19. Web site: 2017 Gödel Prize. European Association for Theoretical Computer Science. EATCS. 29 March 2017.
  20. Calibrating Noise to Sensitivity in Private Data Analysis . Cynthia . Dwork . Frank . McSherry . Kobbi . Nissim . Adam . Smith. 2006 . Theory of Cryptography (TCC). Halevi. Shai. Rabin. Tal. Lecture Notes in Computer Science. 3876 . Springer-Verlag . 265–284 . 978-3-540-32731-8 . 10.1007/11681878_14. free .
  21. Web site: 2018 Gödel Prize citation.
  22. Regev. Oded. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM. 56. 6. 1–40. 10.1145/1568318.1568324. 2009. 10.1.1.215.3543. 207156623.
  23. Web site: 2019 Gödel Prize citation.
  24. Dinur. Irit. The PCP theorem by gap amplification. Journal of the ACM. 54. 3. 12–es. 2007. 10.1145/1236457.1236459. 53244523.
  25. Web site: 2020 Gödel Prize citation.
  26. Journal of the ACM. A constructive proof of the general Lovász Local Lemma. 57. 2. 2010. 0004-5411. 10.1145/1667053.
  27. Web site: 2021 Gödel Prize citation.
  28. Bulatov . Andrei A. . The complexity of the counting constraint satisfaction problem . Journal of the ACM . Association for Computing Machinery . 60 . 5 . 2013 . 0004-5411 . 10.1145/2528400 . 1–41. 8964233 .
  29. Dyer . Martin . Richerby . David . An Effective Dichotomy for the Counting Constraint Satisfaction Problem . SIAM Journal on Computing . Society for Industrial & Applied Mathematics (SIAM) . 42 . 3 . 2013 . 0097-5397 . 10.1137/100811258 . 1245–1274. 1003.3879 . 1247279 .
  30. Cai . Jin-Yi . Chen . Xi . Complexity of Counting CSP with Complex Weights . Journal of the ACM . Association for Computing Machinery . 64 . 3 . 2017-06-22 . 0004-5411 . 10.1145/2822891 . 1–39. 1111.2384 . 1053684 .
  31. Web site: 2022 Gödel Prize citation .
  32. Brakerski . Zvika . Vaikuntanathan . Vinod . January 2014 . Efficient Fully Homomorphic Encryption from (Standard) $\mathsf$ . SIAM Journal on Computing . 43 . 2 . 831–871 . 10.1137/120868669 . 1721.1/115488 . 8831240 . 0097-5397. free .
  33. Book: Brakerski . Zvika . Gentry . Craig . Vaikuntanathan . Vinod . Proceedings of the 3rd Innovations in Theoretical Computer Science Conference . (Leveled) fully homomorphic encryption without bootstrapping . 2012 . http://dx.doi.org/10.1145/2090236.2090262 . 309–325 . New York, New York, USA . ACM Press . 10.1145/2090236.2090262. 9781450311151 . 2602543 .
  34. Web site: 2023 Gödel Prize citation .
  35. Fiorini. Samuel. Massar. Serge. Pokutta. Sebastian. Tiwary. Hans Raj. de Wolf. Ronald. Exponential Lower Bounds for Polytopes in Combinatorial Optimization. Journal of the ACM. 62. 2. 17:1–17:23. 2015. 10.1145/2716307. 7372000. 1111.0837.
  36. Rothvoss. Thomas. The Matching Polytope has Exponential Extension Complexity. Journal of the ACM. 64. 6. 41:1–41:19. 2017. 10.1145/3127497. 1311.2369. 47045361.
  37. Web site: 2024 Gödel Prize citation .
  38. Book: Williams, Ryan . Non-uniform ACC Circuit Lower Bounds . June 2011 . 2011 IEEE 26th Annual Conference on Computational Complexity . http://dx.doi.org/10.1109/ccc.2011.36 . 115–125 . IEEE . 10.1109/ccc.2011.36. 978-1-4577-0179-5 .

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Gödel Prize".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.