Gödel Prize

File:1925 kurt gödel.png

Kurt Gödel

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.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

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.<ref name="Godël2017" />

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,<ref group="paper">Template:Citation</ref> 1989<ref group="paper">Template:Citation</ref>
1994	Johan Håstad	for an exponential lower bound on the size of constant-depth Boolean circuits (for the parity function).	1989<ref group="paper">Template:Citation</ref>
1995	Neil Immerman and Róbert Szelepcsényi	for the Immerman–Szelepcsényi theorem regarding nondeterministic space complexity	1988,<ref group="paper">Template:Citation</ref> 1988<ref group="paper">Template:Citation</ref>
1996	Mark Jerrum and Alistair Sinclair	for work on Markov chains and the approximation of the permanent of a matrix	1989,<ref group="paper">Template:Citation</ref> 1989<ref group="paper">Template:Citation</ref>
1997	Joseph Halpern and Yoram Moses	for defining a formal notion of "knowledge" in distributed environments	1990<ref group="paper">Template:Citation</ref>
1998	Seinosuke Toda	for Toda's theorem, which showed a connection between counting solutions (PP) and alternation of quantifiers (PH)	1991<ref group="paper">Template:Citation</ref>
1999	Peter Shor	for Shor's algorithm for factoring numbers in polynomial time on a quantum computer	1997<ref group="paper">Template:Citation</ref>
2000	Moshe Y. Vardi and Pierre Wolper	for work on temporal logic with finite automata	1994<ref group="paper">Template:Citation</ref>
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,<ref group="paper">Template:Citation</ref> 1998,<ref group="paper">Template:Citation </ref> 1998<ref group="paper">Template:Citation</ref>
2002	Géraud Sénizergues	for proving that equivalence of deterministic pushdown automata is decidable	2001<ref group="paper">Template:Citation</ref>
2003	Yoav Freund and Robert Schapire	for the AdaBoost algorithm in machine learning	1997<ref group="paper">Template:Citation</ref>
2004	Maurice Herlihy, Michael Saks, Nir Shavit and Fotios Zaharoglou	for applications of topology to the theory of distributed computing	1999,<ref group="paper">Template:Citation. Gödel prize lecture</ref> 2000<ref group="paper">Template:Citation</ref>
2005	Noga Alon, Yossi Matias and Mario Szegedy	for their foundational contribution to streaming algorithms	1999<ref group="paper">Template:Citation. First presented at the Symposium on Theory of Computing (STOC) in 1996.</ref>
2006	Manindra Agrawal, Neeraj Kayal, Nitin Saxena	for the AKS primality test	2004<ref group="paper">Template:Citation</ref>
2007	Alexander Razborov, Steven Rudich	for natural proofs	1997<ref group="paper">Template:Citation</ref>
2008	Daniel Spielman, Shang-Hua Teng	for smoothed analysis of algorithms	2004<ref group="paper">Template:Citation</ref>
2009	Omer Reingold, Salil Vadhan, Avi Wigderson	for zig-zag product of graphs and undirected connectivity in log space	2002,<ref group="paper">Template:Citation</ref> 2008<ref group="paper">Template:CitationTemplate:Dead link</ref>
2010	Sanjeev Arora, Joseph S. B. Mitchell	for their concurrent discovery of a polynomial-time approximation scheme for the Euclidean Travelling Salesman Problem	1998,<ref group="paper">Template:Citation</ref> 1999<ref group="paper">Template:Citation</ref>
2011	Johan Håstad	for proving optimal inapproximability results for various combinatorial problems	2001<ref group="paper">Template:Citation</ref>
2012	Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden and Éva Tardos	for laying the foundations of algorithmic game theory<ref name=sigact-2012>Template:Cite news</ref>	2009,<ref group=paper>Template:Cite journal</ref> 2002,<ref group = "paper">Template:Cite journal</ref> 2001<ref group="paper">Template:Cite journal</ref>
2013	Dan Boneh, Matthew K. Franklin, and Antoine Joux	for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography<ref>ACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security Template:Webarchive, Association for Computing Machinery, May 29, 2013.</ref>	2003,<ref group="paper">Template:Cite journal</ref> 2004<ref group="paper">Template:Cite journal</ref>
2014	Ronald Fagin, Template:Interlanguage link, and Moni Naor	for Optimal Aggregation Algorithms for middleware<ref>Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources, Association for Computing Machinery, April 30, 2014.</ref>	2003,<ref group="paper">Template:Cite journal</ref>
2015	Daniel Spielman, Shang-Hua Teng	for their series of papers on nearly-linear-time Laplacian solvers<ref>2015 Gödel Prize announcement Template:Webarchive by Association for Computing Machinery.</ref>	2011<ref group="paper" name="SpielmanTeng2011">Template:Cite journal</ref> 2013<ref group="paper" name="SpielmanTeng2013">Template:Cite journal</ref> 2014<ref group="paper" name="SpielmanTeng2014">Template:Cite journal</ref>
2016	Stephen Brookes and Peter W. O'Hearn	for their invention of Concurrent Separation Logic	2007,<ref group="paper">Template:Cite journal</ref> 2007<ref group="paper">Template:Cite journal</ref>
citation	CitationClass=web }}</ref>	Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith	for the invention of differential privacy	2006<ref group="paper">Template:Cite conference</ref>
citation	CitationClass=web }}</ref>	Oded Regev	for introducing the learning with errors problem	2009<ref group="paper" name="Regev2009">Template:Cite journal</ref>
citation	CitationClass=web }}</ref>	Irit Dinur	for her new proof of the PCP theorem by gap amplification	2007<ref group="paper" name="Dinur2007">Template:Cite journal</ref>
citation	CitationClass=web }}</ref>	Robin Moser and Gábor Tardos	for their constructive proof of the Lovász local lemma	2010<ref group="paper" name="MoserTardos2010">Template:Cite journal</ref>
citation	CitationClass=web }}</ref>	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<ref group="paper" name="Bulatov 2013 pp. 1–41">Template:Cite journal</ref> 2013<ref group="paper" name="Dyer Richerby 2013 pp. 1245–1274">Template:Cite journal</ref> 2017<ref group="paper" name="Cai Chen pp. 1–39">Template:Cite journal</ref>
citation	CitationClass=web }}</ref>	Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan	for their transformative contributions to cryptography by constructing efficient fully homomorphic encryption (FHE) schemes	2014,<ref group="paper" name="BV11">Template:Cite journal</ref> 2014<ref group="paper" name="BGV12">Template:Cite book</ref>
citation	CitationClass=web }}</ref>	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,<ref group="paper" name="FMPTW15"> Template:Cite journal</ref> 2017<ref group="paper" name="Rot17"> Template:Cite journal </ref>
citation	CitationClass=web }}</ref>	Ryan Williams	for his work on circuit lower bounds and the “algorithms to lower bounds” paradigm	2011<ref group="paper">Template:Cite book</ref>

See also

• List of computer science awards

References

• Prize website with list of winners