Gödel Prize
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory. 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 either at STOC or ICALP. To be eligible for the prize, a paper must be published in a refereed journal within the last 14 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.
Recipients
| Year | Name | 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. | 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 and alternation of quantifiers | 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, Shanghua 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 result for various combinatorial problems | 2001 |
| 2012 | Elias Koutsoupias, Christos Papadimitriou, Noam Nisan,, 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,, and Moni Naor | for Optimal Aggregation Algorithms for Middleware | 2003, |
| 2015 | Daniel Spielman, Shanghua 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,, Kobbi Nissim, and | 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 |