# Gödel Prize

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.
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

| 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, 1989 |
| 1994 | Johan Håstad | for an exponential lower bound on the size of constant-depth Boolean circuits (for the parity function). | 1989 |
| 1995 | Neil Immerman and Róbert Szelepcsényi | for the Immerman–Szelepcsényi theorem regarding nondeterministic space complexity | 1988, 1988 |
| 1996 | Mark Jerrum and Alistair Sinclair | for work on Markov chains and the approximation of the permanent of a matrix | 1989, 1989 |
| 1997 | Joseph Halpern and Yoram Moses | for defining a formal notion of "knowledge" in distributed environments | 1990 |
| 1998 | Seinosuke Toda | for Toda's theorem, which showed a connection between counting solutions (PP) and alternation of quantifiers (PH) | 1991 |
| 1999 | Peter Shor | for Shor's algorithm for factoring numbers in polynomial time on a quantum computer | 1997 |
| 2000 | Moshe Y. Vardi and Pierre Wolper | for work on temporal logic with finite automata | 1994 |
| 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, 1998, 1998 |
| 2002 | Géraud Sénizergues | for proving that equivalence of deterministic pushdown automata is decidable | 2001 |
| 2003 | Yoav Freund and Robert Schapire | for the AdaBoost algorithm in machine learning | 1997 |
| 2004 | Maurice Herlihy, Michael Saks, Nir Shavit and Fotios Zaharoglou | for applications of topology to the theory of distributed computing | 1999, 2000 |
| 2005 | Noga Alon, Yossi Matias and Mario Szegedy | for their foundational contribution to streaming algorithms | 1999 |
| 2006 | Manindra Agrawal, Neeraj Kayal, Nitin Saxena | for the AKS primality test | 2004 |
| 2007 | Alexander Razborov, Steven Rudich | for natural proofs | 1997 |
| 2008 | Daniel Spielman, Shang-Hua Teng | for smoothed analysis of algorithms | 2004 |
| 2009 | Omer Reingold, Salil Vadhan, Avi Wigderson | for zig-zag product of graphs and undirected connectivity in log space | 2002, 2008 |
| 2010 | Sanjeev Arora, Joseph S. B. Mitchell | for their concurrent discovery of a polynomial-time approximation scheme for the Euclidean Travelling Salesman Problem | 1998, 1999 |
| 2011 | Johan Håstad | for proving optimal inapproximability results for various combinatorial problems | 2001 |
| 2012 | Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden and Éva Tardos | for laying the foundations of algorithmic game theory | 2009, 2002, 2001 |
| 2013 | Dan Boneh, Matthew K. Franklin, and Antoine Joux | for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography | 2003, 2004 |
| 2014 | Ronald Fagin, Amnon Lotem [fr], and Moni Naor | for Optimal Aggregation Algorithms for middleware | 2003, |
| 2015 | Daniel Spielman, Shang-Hua Teng | for their series of papers on nearly-linear-time Laplacian solvers | 2011 2013 2014 |
| 2016 | Stephen Brookes and Peter W. O'Hearn | for their invention of Concurrent Separation Logic | 2007, 2007 |
| 2017 | Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith | for the invention of differential privacy | 2006 |
| 2018 | Oded Regev | for introducing the learning with errors problem | 2009 |
| 2019 | Irit Dinur | for her new proof of the PCP theorem by gap amplification | 2007 |
| 2020 | Robin Moser and Gábor Tardos | for their constructive proof of the Lovász local lemma | 2010 |
| 2021 | 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 2013 2017 |
| 2022 | Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan | for their transformative contributions to cryptography by constructing efficient fully homomorphic encryption (FHE) schemes | 2014, 2014 |
| 2023 | 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, 2017 |
| 2024 | Ryan Williams | for his work on circuit lower bounds and the “algorithms to lower bounds” paradigm | 2011 |

## Winning papers

* ↑ Babai, László; Moran, Shlomo (1988), "Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class" (PDF), Journal of Computer and System Sciences, 36 (2): 254–276, doi:10.1016/0022-0000(88)90028-1, ISSN 0022-0000
* ↑ Goldwasser, S.; Micali, S.; Rackoff, C. (1989), "The knowledge complexity of interactive proof systems" (PDF), SIAM Journal on Computing, 18 (1): 186–208, CiteSeerX 10.1.1.397.4002, doi:10.1137/0218012, ISSN 1095-7111
* ↑ Håstad, Johan (1989), "Almost Optimal Lower Bounds for Small Depth Circuits" (PDF), in Micali, Silvio (ed.), Randomness and Computation, Advances in Computing Research, vol. 5, JAI Press, pp. 6–20, ISBN 978-0-89232-896-3, archived from the original (PDF) on 2012-02-22
* ↑ Immerman, Neil (1988), "Nondeterministic space is closed under complementation" (PDF), SIAM Journal on Computing, 17 (5): 935–938, CiteSeerX 10.1.1.54.5941, doi:10.1137/0217058, ISSN 1095-7111
* ↑ Szelepcsényi, R. (1988), "The method of forced enumeration for nondeterministic automata" (PDF), Acta Informatica, 26 (3): 279–284, doi:10.1007/BF00299636, hdl:10338.dmlcz/120489, S2CID 10838178
* ↑ Sinclair, A.; Jerrum, M. (1989), "Approximate counting, uniform generation and rapidly mixing Markov chains", Information and Computation, 82 (1): 93–133, doi:10.1016/0890-5401(89)90067-9, ISSN 0890-5401
* ↑ Jerrum, M.; Sinclair, Alistair (1989), "Approximating the permanent", SIAM Journal on Computing, 18 (6): 1149–1178, CiteSeerX 10.1.1.431.4190, doi:10.1137/0218077, ISSN 1095-7111
* ↑ Halpern, Joseph; Moses, Yoram (1990), "Knowledge and common knowledge in a distributed environment" (PDF), Journal of the ACM, 37 (3): 549–587, arXiv:cs/0006009, doi:10.1145/79147.79161, S2CID 52151232
* ↑ Toda, Seinosuke (1991), "PP is as hard as the polynomial-time hierarchy" (PDF), SIAM Journal on Computing, 20 (5): 865–877, CiteSeerX 10.1.1.121.1246, doi:10.1137/0220053, ISSN 1095-7111, archived from the original (PDF) on 2016-03-03, retrieved 2010-06-08
* ↑ Shor, Peter W. (1997), "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM Journal on Computing, 26 (5): 1484–1509, arXiv:quant-ph/9508027, doi:10.1137/S0097539795293172, ISSN 1095-7111, S2CID 2337707
* ↑ Vardi, Moshe Y.; Wolper, Pierre (1994), "Reasoning about infinite computations" (PDF), Information and Computation, 115 (1): 1–37, doi:10.1006/inco.1994.1092, ISSN 0890-5401, archived from the original (PDF) on 2011-08-25
* ↑ Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996), "Interactive proofs and the hardness of approximating cliques" (PDF), Journal of the ACM, 43 (2): 268–292, doi:10.1145/226643.226652, ISSN 0004-5411
* ↑ Arora, Sanjeev; Safra, Shmuel (1998), "Probabilistic checking of proofs: a new characterization of NP" (PDF), Journal of the ACM, 45 (1): 70–122, doi:10.1145/273865.273901, ISSN 0004-5411, S2CID 751563, archived from the original (PDF) on 2011-06-10
* ↑ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), "Proof verification and the hardness of approximation problems" (PDF), Journal of the ACM, 45 (3): 501–555, CiteSeerX 10.1.1.145.4652, doi:10.1145/278298.278306, ISSN 0004-5411, S2CID 8561542, archived from the original (PDF) on 2011-06-10
* ↑ Sénizergues, Géraud (2001), "L(A) = L(B)? decidability results from complete formal systems", Theor. Comput. Sci., 251 (1): 1–166, doi:10.1016/S0304-3975(00)00285-1, ISSN 0304-3975
* ↑ Freund, Y.; Schapire, R.E. (1997), "A decision-theoretic generalization of on-line learning and an application to boosting" (PDF), Journal of Computer and System Sciences, 55 (1): 119–139, doi:10.1006/jcss.1997.1504, ISSN 1090-2724
* ↑ Herlihy, Maurice; Shavit, Nir (1999), "The topological structure of asynchronous computability" (PDF), Journal of the ACM, 46 (6): 858–923, CiteSeerX 10.1.1.78.1455, doi:10.1145/331524.331529, S2CID 5797174. Gödel prize lecture
* ↑ Saks, Michael; Zaharoglou, Fotios (2000), "Wait-free k-set agreement is impossible: The topology of public knowledge", SIAM Journal on Computing, 29 (5): 1449–1483, doi:10.1137/S0097539796307698
* ↑ Alon, Noga; Matias, Yossi; Szegedy, Mario (1999), "The space complexity of approximating the frequency moments" (PDF), Journal of Computer and System Sciences, 58 (1): 137–147, doi:10.1006/jcss.1997.1545. First presented at the Symposium on Theory of Computing (STOC) in 1996.
* ↑ Agrawal, M.; Kayal, N.; Saxena, N. (2004), "PRIMES is in P", Annals of Mathematics, 160 (2): 781–793, doi:10.4007/annals.2004.160.781, ISSN 0003-486X
* ↑ Razborov, Alexander A.; Rudich, Steven (1997), "Natural proofs", Journal of Computer and System Sciences, 55 (1): 24–35, doi:10.1006/jcss.1997.1494, ISSN 0022-0000, ECCC TR94-010
* ↑ Spielman, Daniel A.; Teng, Shang-Hua (2004), "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time", J. ACM, 51 (3): 385–463, arXiv:math/0212413, doi:10.1145/990308.990310, ISSN 0004-5411
* ↑ Reingold, Omer; Vadhan, Salil; Wigderson, Avi (2002), "Entropy waves, the zig-zag graph product, and new constant-degree expanders", Annals of Mathematics, 155 (1): 157–187, CiteSeerX 10.1.1.236.8669, doi:10.2307/3062153, ISSN 0003-486X, JSTOR 3062153, MR 1888797, S2CID 120739405
* ↑ Reingold, Omer (2008), "Undirected connectivity in log-space", J. ACM, 55 (4): 1–24, doi:10.1145/1391289.1391291, ISSN 0004-5411, S2CID 207168478
* ↑ Arora, Sanjeev (1998), "Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems", Journal of the ACM, 45 (5): 753–782, CiteSeerX 10.1.1.23.6765, doi:10.1145/290179.290180, ISSN 0004-5411, S2CID 3023351
* ↑ Mitchell, Joseph S. B. (1999), "Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems", SIAM Journal on Computing, 28 (4): 1298–1309, doi:10.1137/S0097539796309764, ISSN 1095-7111
* ↑ Håstad, Johan (2001), "Some optimal inapproximability results" (PDF), Journal of the ACM, 48 (4): 798–859, CiteSeerX 10.1.1.638.2808, doi:10.1145/502090.502098, ISSN 0004-5411, S2CID 5120748
* ↑ Koutsoupias, Elias; Papadimitriou, Christos (2009). "Worst-case equilibria". Computer Science Review. 3 (2): 65–69. doi:10.1016/j.cosrev.2009.04.003.
* ↑ Roughgarden, Tim; Tardos, Éva (2002). "How bad is selfish routing?". Journal of the ACM. 49 (2): 236–259. CiteSeerX 10.1.1.147.1081. doi:10.1145/506147.506153. S2CID 207638789.
* ↑ Nisan, Noam; Ronen, Amir (2001). "Algorithmic Mechanism Design". Games and Economic Behavior. 35 (1–2): 166–196. CiteSeerX 10.1.1.21.1731. doi:10.1006/game.1999.0790.
* ↑ Boneh, Dan; Franklin, Matthew (2003). "Identity-based encryption from the Weil pairing". SIAM Journal on Computing. 32 (3): 586–615. CiteSeerX 10.1.1.66.1131. doi:10.1137/S0097539701398521. MR 2001745.
* ↑ Joux, Antoine (2004). "A one round protocol for tripartite Diffie-Hellman". Journal of Cryptology. 17 (4): 263–276. doi:10.1007/s00145-004-0312-y. MR 2090557. S2CID 3350730.
* ↑ Fagin, Ronald; Lotem, Amnon; Naor, Moni (2003). "Optimal aggregation algorithms for middleware". Journal of Computer and System Sciences. 66 (4): 614–656. arXiv:cs/0204046. doi:10.1016/S0022-0000(03)00026-6.
* ↑ Spielman, Daniel A.; Teng, Shang-Hua (2011). "Spectral Sparsification of Graphs". SIAM Journal on Computing. 40 (4): 981–1025. arXiv:0808.4134. doi:10.1137/08074489X. ISSN 0097-5397. S2CID 9646279.
* ↑ Spielman, Daniel A.; Teng, Shang-Hua (2013). "A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning". SIAM Journal on Computing. 42 (1): 1–26. arXiv:0809.3232. doi:10.1137/080744888. ISSN 0097-5397. S2CID 9151077.
* ↑ Spielman, Daniel A.; Teng, Shang-Hua (2014). "Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems". SIAM Journal on Matrix Analysis and Applications. 35 (3): 835–885. arXiv:cs/0607105. doi:10.1137/090771430. ISSN 0895-4798. S2CID 1750944.
* ↑ Brookes, Stephen (2007). "A Semantics for Concurrent Separation Logic" (PDF). Theoretical Computer Science. 375 (1–3): 227–270. doi:10.1016/j.tcs.2006.12.034.
* ↑ O'Hearn, Peter (2007). "Resources, Concurrency and Local Reasoning" (PDF). Theoretical Computer Science. 375 (1–3): 271–307. doi:10.1016/j.tcs.2006.12.035.
* ↑ Dwork, Cynthia; McSherry, Frank; Nissim, Kobbi; Smith, Adam (2006). Halevi, Shai; Rabin, Tal (eds.). Calibrating Noise to Sensitivity in Private Data Analysis. Theory of Cryptography (TCC). Lecture Notes in Computer Science. Vol. 3876. Springer-Verlag. pp. 265–284. doi:10.1007/11681878_14. ISBN 978-3-540-32731-8.
* ↑ Regev, Oded (2009). "On lattices, learning with errors, random linear codes, and cryptography". Journal of the ACM. 56 (6): 1–40. CiteSeerX 10.1.1.215.3543. doi:10.1145/1568318.1568324. S2CID 207156623.
* ↑ Dinur, Irit (2007). "The PCP theorem by gap amplification". Journal of the ACM. 54 (3): 12–es. doi:10.1145/1236457.1236459. S2CID 53244523.
* ↑ "A constructive proof of the general Lovász Local Lemma". Journal of the ACM. 57 (2). 2010. doi:10.1145/1667053. ISSN 0004-5411.
* ↑ Bulatov, Andrei A. (2013). "The complexity of the counting constraint satisfaction problem". Journal of the ACM. 60 (5). Association for Computing Machinery: 1–41. doi:10.1145/2528400. ISSN 0004-5411. S2CID 8964233.
* ↑ Dyer, Martin; Richerby, David (2013). "An Effective Dichotomy for the Counting Constraint Satisfaction Problem". SIAM Journal on Computing. 42 (3). Society for Industrial & Applied Mathematics (SIAM): 1245–1274. arXiv:1003.3879. doi:10.1137/100811258. ISSN 0097-5397. S2CID 1247279.
* ↑ Cai, Jin-Yi; Chen, Xi (2017-06-22). "Complexity of Counting CSP with Complex Weights". Journal of the ACM. 64 (3). Association for Computing Machinery: 1–39. arXiv:1111.2384. doi:10.1145/2822891. ISSN 0004-5411. S2CID 1053684.
* ↑ Brakerski, Zvika; Vaikuntanathan, Vinod (January 2014). "Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$". SIAM Journal on Computing. 43 (2): 831–871. doi:10.1137/120868669. hdl:1721.1/115488. ISSN 0097-5397. S2CID 8831240.
* ↑ Brakerski, Zvika; Gentry, Craig; Vaikuntanathan, Vinod (2012). "(Leveled) fully homomorphic encryption without bootstrapping". Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. New York, New York, USA: ACM Press. pp. 309–325. doi:10.1145/2090236.2090262. ISBN 9781450311151. 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. arXiv:1111.0837. doi:10.1145/2716307. S2CID 7372000.
* ↑ Rothvoss, Thomas (2017). "The Matching Polytope has Exponential Extension Complexity". Journal of the ACM. 64 (6): 41:1–41:19. arXiv:1311.2369. doi:10.1145/3127497. S2CID 47045361.
* ↑ Williams, Ryan (June 2011). "Non-uniform ACC Circuit Lower Bounds". 2011 IEEE 26th Annual Conference on Computational Complexity. IEEE. pp. 115–125. doi:10.1109/ccc.2011.36. ISBN 978-1-4577-0179-5.