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) NotesPublication year1993 László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran, and Charles Rackoff for the development of interactive proof systems 1988, 19891994 Johan Håstad for an exponential lower bound on the size of constant-depth Boolean circuits (for the parity function). 19891995 Neil Immerman and Róbert Szelepcsényi for the Immerman–Szelepcsényi theorem regarding nondeterministic space complexity 1988, 19881996 Mark Jerrum and Alistair Sinclair for work on Markov chains and the approximation of the permanent of a matrix 1989, 19891997 Joseph Halpern and Yoram Moses for defining a formal notion of "knowledge" in distributed environments 19901998 Seinosuke Toda for Toda's theorem, which showed a connection between counting solutions (PP) and alternation of quantifiers (PH) 19911999 Peter Shor for Shor's algorithm for factoring numbers in polynomial time on a quantum computer 19972000 Moshe Y. Vardi and Pierre Wolper for work on temporal logic with finite automata 19942001 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, 19982002 Géraud Sénizergues for proving that equivalence of deterministic pushdown automata is decidable 20012003 Yoav Freund and Robert Schapire for the AdaBoost algorithm in machine learning 19972004 Maurice Herlihy, Michael Saks, Nir Shavit and Fotios Zaharoglou for applications of topology to the theory of distributed computing 1999,. Gödel prize lecture 20002005 Noga Alon, Yossi Matias and Mario Szegedy for their foundational contribution to streaming algorithms 1999. First presented at the Symposium on Theory of Computing (STOC) in 1996.2006 Manindra Agrawal, Neeraj Kayal, Nitin Saxena for the AKS primality test 20042007 Alexander Razborov, Steven Rudich for natural proofs 19972008 Daniel Spielman, Shang-Hua Tengfor smoothed analysis of algorithms 20042009 Omer Reingold, Salil Vadhan, Avi Wigderson for zig-zag product of graphs and undirected connectivity in log space 2002, 20082010 Sanjeev Arora, Joseph S. B. Mitchell for their concurrent discovery of a polynomial-time approximation scheme for the Euclidean Travelling Salesman Problem 1998, 19992011 Johan Håstad for proving optimal inapproximability results for various combinatorial problems 20012012 Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden and Éva Tardos for laying the foundations of algorithmic game theory 2009, 2002, 20012013 Dan Boneh, Matthew K. Franklin, and Antoine Joux for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptographyACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security , Association for Computing Machinery, May 29, 2013. 2003, 20042014 Ronald Fagin, , and Moni Naor for Optimal Aggregation Algorithms for middleware Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources, Association for Computing Machinery, April 30, 2014. 2003,2015 Daniel Spielman, Shang-Hua Teng for their series of papers on nearly-linear-time Laplacian solvers2015 Gödel Prize announcement by Association for Computing Machinery. 2011 2013 20142016Stephen Brookes and Peter W. O'Hearnfor their invention of Concurrent Separation Logic2007, 20072017Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smithfor the invention of differential privacy20062018 Oded Regevfor introducing the learning with errors problem20092019 Irit Dinurfor her new proof of the PCP theorem by gap amplification20072020 Robin Moser and Gábor Tardos for their constructive proof of the Lovász local lemma20102021 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 problems2013 2013 20172022Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathanfor their transformative contributions to cryptography by constructing efficient fully homomorphic encryption (FHE) schemes2014, 20142023Samuel Fiorini, Serge Massar, and Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf, and Thomas Rothvossfor showing that any extended formulation for the TSP polytope or the Matching polytope has exponential size2015, 20172024Ryan Williamsfor his work on circuit lower bounds and the “algorithms to lower bounds” paradigm20112025Eshan Chattopadhyay and David Zuckermanfor their work constructing "an explicit two-source extractor with polylogarithmic min-entropy, resolving a central problem in the theory of computation that had been open for almost three decades."20162026Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewartfor efficient algorithms to learn high-dimensional distributions in the presence of adversarial corruptions2019
Winning papers
See also
List of computer science awards
Notes
References Prize website with list of winners