Gödel Prize

File:1925_kurt_gödel.png

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.{{Cite web | url=https://rjlipton.wordpress.com/the-gdel-letter/ | title=The Gödel Letter| date=2009-02-12}}

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

class="wikitable sortable" !Year !width=40% class="unsortable"\| Name(s) !width=45% class="unsortable"\| Notes !Publication year
valign="top" \|1993	László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran, and Charles Rackoff	for the development of interactive proof systems	1988,{{Citation \| last1=Babai \| first1=László \| last2=Moran \| first2=Shlomo \| title=Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class \| url=http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC01/AMgames-Babai-Moran.pdf \| year=1988 \| journal=Journal of Computer and System Sciences \| issn=0022-0000 \| volume=36 \| issue=2 \| pages=254–276 \| doi=10.1016/0022-0000(88)90028-1\| doi-access=free }} 1989{{Citation \| last1=Goldwasser \| first1=S. \| last2=Micali \| first2=S. \| last3=Rackoff \| first3=C. \| title=The knowledge complexity of interactive proof systems \| url=http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC02/GMR89.pdf \| year=1989 \| journal=SIAM Journal on Computing \| issn=1095-7111 \| volume=18 \| issue=1 \| pages=186–208 \| doi=10.1137/0218012\| citeseerx=10.1.1.397.4002 }}
valign="top" \|1994	Johan Håstad	for an exponential lower bound on the size of constant-depth Boolean circuits (for the parity function).	1989{{Citation \| last1=Håstad \| first1=Johan \| series=Advances in Computing Research \| volume=5 \| title=Randomness and Computation \| editor-first=Silvio \| editor-last=Micali \| chapter-url=http://reference.kfupm.edu.sa/content/a/l/almost_optimal_lower_bounds_for_small_de_134215.pdf \| publisher=JAI Press \| year=1989 \| chapter=Almost Optimal Lower Bounds for Small Depth Circuits \| pages=6–20 \| isbn=978-0-89232-896-3 \| url-status=dead \| archive-url=https://web.archive.org/web/20120222163102/http://reference.kfupm.edu.sa/content/a/l/almost_optimal_lower_bounds_for_small_de_134215.pdf \| archive-date=2012-02-22 }}
valign=top \|1995	Neil Immerman and Róbert Szelepcsényi	for the Immerman–Szelepcsényi theorem regarding nondeterministic space complexity	1988,{{Citation \| last1=Immerman \| first1=Neil \| author1-link=Neil Immerman \| title=Nondeterministic space is closed under complementation \| url=http://www.cs.umass.edu/~immerman/pub/space.pdf \| year=1988 \| journal=SIAM Journal on Computing \| issn=1095-7111 \| volume=17 \| issue=5 \| pages=935–938 \| doi=10.1137/0217058\| citeseerx=10.1.1.54.5941 }} 1988{{Citation \| last1=Szelepcsényi \| first1=R. \| title=The method of forced enumeration for nondeterministic automata \| year=1988 \| journal=Acta Informatica \| volume=26 \| issue=3 \| pages=279–284 \| doi=10.1007/BF00299636\| hdl=10338.dmlcz/120489 \| s2cid=10838178 \| url=http://dml.cz/bitstream/handle/10338.dmlcz/120489/ActaOstrav_03-1995-1_10.pdf }}
valign="top" \|1996	Mark Jerrum and Alistair Sinclair	for work on Markov chains and the approximation of the permanent of a matrix	1989,{{Citation \| last1=Sinclair \| first1=A. \| last2=Jerrum \| first2=M. \| title=Approximate counting, uniform generation and rapidly mixing Markov chains \| year=1989 \| journal=Information and Computation \| issn=0890-5401 \| volume=82 \| issue=1 \| pages=93–133 \| doi=10.1016/0890-5401(89)90067-9\| doi-access=free }} 1989{{Citation \| last1=Jerrum \| first1=M. \| last2=Sinclair \| first2=Alistair \| title=Approximating the permanent \| year=1989 \| journal=SIAM Journal on Computing \| issn=1095-7111 \| volume=18 \| issue=6 \| pages=1149–1178 \| doi=10.1137/0218077\| citeseerx=10.1.1.431.4190 }}
valign="top" \|1997	Joseph Halpern and Yoram Moses	for defining a formal notion of "knowledge" in distributed environments	1990{{Citation \| last1=Halpern \| first1=Joseph \| author-link1=Joseph Halpern \| last2=Moses \| first2=Yoram \| author-link2=Yoram Moses \| title=Knowledge and common knowledge in a distributed environment \| journal=Journal of the ACM \| volume=37 \| year=1990 \| pages=549–587 \| url=https://www.cs.cornell.edu/home/halpern/papers/common_knowledge.pdf \| doi=10.1145/79147.79161 \| issue=3 \| arxiv=cs/0006009\| s2cid=52151232 }}
valign="top" \|1998	Seinosuke Toda	for Toda's theorem, which showed a connection between counting solutions (PP) and alternation of quantifiers (PH)	1991{{Citation \| last1=Toda \| first1=Seinosuke \| title=PP is as hard as the polynomial-time hierarchy \| url=http://faculty.cs.tamu.edu/chen/courses/637/2008/pres/korben.pdf \| year=1991 \| journal=SIAM Journal on Computing \| issn=1095-7111 \| volume=20 \| issue=5 \| pages=865–877 \| doi=10.1137/0220053 \| citeseerx=10.1.1.121.1246 \| access-date=2010-06-08 \| archive-date=2016-03-03 \| archive-url=https://web.archive.org/web/20160303170125/http://faculty.cs.tamu.edu/chen/courses/637/2008/pres/korben.pdf \| url-status=dead }}
valign="top" \|1999	Peter Shor	for Shor's algorithm for factoring numbers in polynomial time on a quantum computer	1997{{Citation \| last1=Shor \| first1=Peter W. \| title=Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer \| year=1997 \| journal=SIAM Journal on Computing \| issn=1095-7111 \| volume=26 \| issue=5 \| pages=1484–1509 \| doi=10.1137/S0097539795293172 \| arxiv=quant-ph/9508027 \| s2cid=2337707 }}
valign="top" \|2000	Moshe Y. Vardi and Pierre Wolper	for work on temporal logic with finite automata	1994{{Citation \| last1=Vardi \| first1=Moshe Y. \| last2=Wolper \| first2=Pierre \| title=Reasoning about infinite computations \| url=http://reference.kfupm.edu.sa/content/r/e/reasoning_about_infinite_computations__102167.pdf \| year=1994 \| journal=Information and Computation \| issn=0890-5401 \| volume=115 \| issue=1 \| pages=1–37 \| doi=10.1006/inco.1994.1092 \| url-status=dead \| archive-url=https://web.archive.org/web/20110825210914/http://reference.kfupm.edu.sa/content/r/e/reasoning_about_infinite_computations__102167.pdf \| archive-date=2011-08-25 }}
valign="top" \|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,{{Citation \| last1=Feige \| first1=Uriel \| last2=Goldwasser \| first2=Shafi \| last3=Lovász \| first3=Laszlo \| last4=Safra \| first4=Shmuel \| last5=Szegedy \| first5=Mario \| title=Interactive proofs and the hardness of approximating cliques \| url=http://groups.csail.mit.edu/cis/pubs/shafi/1996-jacm.pdf \| year=1996 \| journal=Journal of the ACM \| issn=0004-5411 \| volume=43 \| issue=2 \| pages=268–292 \| doi=10.1145/226643.226652\| doi-access=free }} 1998,{{Citation \| last1=Arora \| first1=Sanjeev \| last2=Safra \| first2=Shmuel \| title=Probabilistic checking of proofs: a new characterization of NP \| url=http://www.cs.umd.edu/~gasarch/pcp/AS.pdf \| year=1998 \| journal=Journal of the ACM \| issn=0004-5411 \| volume=45 \| issue=1 \| pages=70–122 \| doi=10.1145/273865.273901 \| s2cid=751563 \| url-status=dead \| archive-url=https://web.archive.org/web/20110610101051/http://www.cs.umd.edu/~gasarch/pcp/AS.pdf \| archive-date=2011-06-10 }} 1998{{Citation \| last1=Arora \| first1=Sanjeev \| last2=Lund \| first2=Carsten \| last3=Motwani \| first3=Rajeev \| last4=Sudan \| first4=Madhu \| last5=Szegedy \| first5=Mario \| title=Proof verification and the hardness of approximation problems \| url=https://www.cs.umd.edu/~gasarch/pcp/ALMSS.pdf \| year=1998 \| journal=Journal of the ACM \| issn=0004-5411 \| volume=45 \| issue=3 \| pages=501–555 \| doi=10.1145/278298.278306 \| url-status=dead \| archive-url=https://web.archive.org/web/20110610101241/https://www.cs.umd.edu/~gasarch/pcp/ALMSS.pdf \| archive-date=2011-06-10 \| citeseerx=10.1.1.145.4652 \| s2cid=8561542 }}
valign="top" \|2002	Géraud Sénizergues	for proving that equivalence of deterministic pushdown automata is decidable	2001{{Citation \| last1=Sénizergues \| first1=Géraud \| title=L(A) = L(B)? decidability results from complete formal systems \| year=2001 \| journal=Theor. Comput. Sci. \| issn=0304-3975 \| volume=251 \| issue=1 \| pages=1–166 \| doi=10.1016/S0304-3975(00)00285-1\| doi-access= }}
valign="top" \|2003	Yoav Freund and Robert Schapire	for the AdaBoost algorithm in machine learning	1997{{Citation \| last1=Freund \| first1=Y. \| last2=Schapire \| first2=R.E. \| title=A decision-theoretic generalization of on-line learning and an application to boosting \| url=http://www-ai.cs.tu-dortmund.de/LEHRE/PG/PG445/literatur/freund_schapire_97a.pdf \| year=1997 \| journal=Journal of Computer and System Sciences \| issn=1090-2724 \| volume=55 \| issue=1 \| pages=119–139 \| doi=10.1006/jcss.1997.1504}}
valign="top" \|2004	Maurice Herlihy, Michael Saks, Nir Shavit and Fotios Zaharoglou	for applications of topology to the theory of distributed computing	1999,{{Citation \| last1=Herlihy \| first1=Maurice \| author-link1=Maurice Herlihy \| last2=Shavit \| first2=Nir \| author-link2=Nir Shavit \| title=The topological structure of asynchronous computability \| journal=Journal of the ACM \| volume=46 \| year=1999 \| pages=858–923 \| doi=10.1145/331524.331529 \| url=http://www.cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf \| issue=6 \| citeseerx=10.1.1.78.1455 \| s2cid=5797174 }}. [http://www.cs.brown.edu/~mph/finland.pdf Gödel prize lecture] 2000{{Citation \| title=Wait-free k-set agreement is impossible: The topology of public knowledge \| last1=Saks \| first1=Michael \| author-link1=Michael Saks (mathematician) \| last2=Zaharoglou \| first2=Fotios \| author-link2=Fotios Zaharoglou \| journal=SIAM Journal on Computing \| volume=29 \| year=2000 \| pages=1449–1483 \| doi=10.1137/S0097539796307698 \| issue=5 }}
valign="top" \|2005	Noga Alon, Yossi Matias and Mario Szegedy	for their foundational contribution to streaming algorithms	1999{{Citation \| last1=Alon \| first1=Noga \| author1-link=Noga Alon \| last2=Matias \| first2=Yossi \| last3=Szegedy \| first3=Mario \| journal=Journal of Computer and System Sciences \| url=http://www.math.tau.ac.il/~noga/PDFS/amsz4.pdf \| year=1999 \| title=The space complexity of approximating the frequency moments \| volume=58 \| issue=1 \| pages=137–147 \| doi=10.1006/jcss.1997.1545}}. First presented at the Symposium on Theory of Computing (STOC) in 1996.
valign="top" \|2006	Manindra Agrawal, Neeraj Kayal, Nitin Saxena	for the AKS primality test	2004{{Citation \| last1=Agrawal \| first1=M. \| last2=Kayal \| first2=N. \| last3=Saxena \| first3=N. \| title=PRIMES is in P \| year=2004 \| journal=Annals of Mathematics \| issn=0003-486X \| volume=160 \| pages=781–793 \| doi=10.4007/annals.2004.160.781 \| issue=2 \| doi-access=free }}
valign="top" \|2007	Alexander Razborov, Steven Rudich	for natural proofs	1997{{Citation \| last1=Razborov \| first1=Alexander A. \| last2=Rudich \| first2=Steven \| title=Natural proofs \| id={{ECCC\|1994\|94\|010}} \| year=1997 \| journal=Journal of Computer and System Sciences \| issn=0022-0000 \| volume=55 \| issue=1 \| pages=24–35 \| doi=10.1006/jcss.1997.1494\| doi-access=free }}
valign="top" \|2008	Daniel Spielman, Shang-Hua Teng	for smoothed analysis of algorithms	2004{{Citation \| last1=Spielman \| first1=Daniel A. \| last2=Teng \| first2=Shang-Hua \| author2-link=Shanghua Teng \| title=Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time \| year=2004 \| journal=J. ACM \| issn=0004-5411 \| volume=51 \| issue=3 \| pages=385–463 \| doi=10.1145/990308.990310 \| arxiv=math/0212413 }}
valign="top" \|2009	Omer Reingold, Salil Vadhan, Avi Wigderson	for zig-zag product of graphs and undirected connectivity in log space	2002,{{Citation \| last1=Reingold \| first1=Omer \| last2=Vadhan \| first2=Salil \| last3=Wigderson \| first3=Avi \| title=Entropy waves, the zig-zag graph product, and new constant-degree expanders \| mr=1888797 \| year=2002 \| journal=Annals of Mathematics \| issn=0003-486X \| volume=155 \| issue=1 \| pages=157–187 \| doi=10.2307/3062153 \| jstor=3062153 \| citeseerx=10.1.1.236.8669 \| s2cid=120739405 }} 2008{{Citation \| last1=Reingold \| first1=Omer \| title=Undirected connectivity in log-space \| url=http://www.weizmann.ac.il/mathusers/reingold/publications/sl.ps \| year=2008 \| journal=J. ACM \| issn=0004-5411 \| volume=55 \| issue=4 \| pages=1–24 \| doi=10.1145/1391289.1391291 \| s2cid=207168478 }}{{dead link\|date=December 2017 \|bot=InternetArchiveBot \|fix-attempted=yes }}
valign="top" \|2010	Sanjeev Arora, Joseph S. B. Mitchell	for their concurrent discovery of a polynomial-time approximation scheme for the Euclidean Travelling Salesman Problem	1998,{{Citation \| last1=Arora \| first1=Sanjeev \| author1-link=Sanjeev Arora \| title=Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems \| doi=10.1145/290179.290180 \| year=1998 \| journal=Journal of the ACM \| issn=0004-5411 \| volume=45 \| issue=5 \| pages=753–782\| citeseerx=10.1.1.23.6765 \| s2cid=3023351 }} 1999{{Citation \| last1=Mitchell \| first1=Joseph S. B. \| author-link=Joseph S. B. Mitchell \| title=Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems \| doi=10.1137/S0097539796309764 \| year=1999 \| journal=SIAM Journal on Computing \| issn=1095-7111 \| volume=28 \| issue=4 \| pages=1298–1309}}
valign="top" \|2011	Johan Håstad	for proving optimal inapproximability results for various combinatorial problems	2001{{Citation \| last1=Håstad \| first1=Johan \| author1-link=Johan Håstad \| title=Some optimal inapproximability results \| doi=10.1145/502090.502098 \| year=2001 \| journal=Journal of the ACM \| issn=0004-5411 \| volume=48 \| issue=4 \| pages=798–859 \| url=http://www.csc.kth.se/~johanh/optimalinap.pdf\| citeseerx=10.1.1.638.2808 \| s2cid=5120748 }}
valign="top" \|2012	Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden and Éva Tardos	for laying the foundations of algorithmic game theory{{cite news\|title=Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory\|url=http://www.acm.org/press-room/news-releases/2012/goedel-prize-2012\|access-date=16 May 2012\|date=16 May 2012\|url-status=dead\|archive-url=https://web.archive.org/web/20130718154540/http://www.acm.org/press-room/news-releases/2012/goedel-prize-2012\|archive-date=18 July 2013}}	2009,{{cite journal\|last=Koutsoupias\|first=Elias\|author2=Papadimitriou, Christos\|title=Worst-case equilibria\|journal=Computer Science Review\|year=2009\|volume=3\|issue=2\|pages=65–69\|doi=10.1016/j.cosrev.2009.04.003}} 2002,{{cite journal\|last=Roughgarden\|first=Tim\|author2=Tardos, Éva\|title=How bad is selfish routing?\|journal=Journal of the ACM\|year=2002\|volume=49\|issue=2\|pages=236–259\|doi=10.1145/506147.506153\|citeseerx=10.1.1.147.1081\|s2cid=207638789}} 2001{{cite journal\|last=Nisan\|first=Noam\|author2=Ronen, Amir\|title=Algorithmic Mechanism Design\|journal=Games and Economic Behavior\|year=2001\|volume=35\|issue=1–2\|pages=166–196\|doi=10.1006/game.1999.0790\|citeseerx=10.1.1.21.1731}}
valign="top" \|2013	Dan Boneh, Matthew K. Franklin, and Antoine Joux	for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography[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] {{webarchive\|url=https://web.archive.org/web/20130601191333/http://www.acm.org/press-room/news-releases/2013/goedel-prize-13 \|date=2013-06-01 }}, Association for Computing Machinery, May 29, 2013.	2003,{{cite journal \| last1 = Boneh \| first1 = Dan \| last2 = Franklin \| first2 = Matthew \| doi = 10.1137/S0097539701398521 \| issue = 3 \| journal = SIAM Journal on Computing \| mr = 2001745 \| pages = 586–615 \| title = Identity-based encryption from the Weil pairing \| volume = 32 \| year = 2003\| citeseerx = 10.1.1.66.1131 }} 2004{{cite journal \| last = Joux \| first = Antoine \| doi = 10.1007/s00145-004-0312-y \| issue = 4 \| journal = Journal of Cryptology \| mr = 2090557 \| pages = 263–276 \| title = A one round protocol for tripartite Diffie-Hellman \| volume = 17 \| year = 2004\| s2cid = 3350730 \| doi-access = free }}
valign="top" \|2014	Ronald Fagin, {{Interlanguage link\|Amnon Lotem\|fr}}, and Moni Naor	for Optimal Aggregation Algorithms for middleware[https://eatcs.org/index.php/component/content/article/1-news/1908-goedel-prize-2014 Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources], Association for Computing Machinery, April 30, 2014.	2003,{{cite journal \| last1 = Fagin \| first1 = Ronald \| last2 = Lotem \| first2 = Amnon \| last3 = Naor \| first3 = Moni \| doi = 10.1016/S0022-0000(03)00026-6 \| issue = 4 \| journal = Journal of Computer and System Sciences \| pages = 614–656 \| title = Optimal aggregation algorithms for middleware \| volume = 66 \| year = 2003\| arxiv = cs/0204046 }}
valign="top" \|2015	Daniel Spielman, Shang-Hua Teng	for their series of papers on nearly-linear-time Laplacian solvers[http://www.sigact.org/Prizes/Godel/citation2015.pdf 2015 Gödel Prize announcement] {{Webarchive\|url=https://web.archive.org/web/20171209021752/http://www.sigact.org/Prizes/Godel/citation2015.pdf \|date=2017-12-09 }} by Association for Computing Machinery.	2011{{cite journal\|last1=Spielman\|first1=Daniel A.\|last2=Teng\|first2=Shang-Hua\|title=Spectral Sparsification of Graphs\|journal=SIAM Journal on Computing\|volume=40\|issue=4\|year=2011\|pages=981–1025\|issn=0097-5397\|doi=10.1137/08074489X\|arxiv=0808.4134\|s2cid=9646279}} 2013{{cite journal\|last1=Spielman\|first1=Daniel A.\|last2=Teng\|first2=Shang-Hua\|title=A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning\|journal=SIAM Journal on Computing\|volume=42\|issue=1\|year=2013\|pages=1–26\|issn=0097-5397\|doi=10.1137/080744888\|arxiv=0809.3232\|s2cid=9151077}} 2014{{cite journal\|last1=Spielman\|first1=Daniel A.\|last2=Teng\|first2=Shang-Hua\|title=Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems\|journal=SIAM Journal on Matrix Analysis and Applications\|volume=35\|issue=3\|year=2014\|pages=835–885\|issn=0895-4798\|doi=10.1137/090771430\|arxiv=cs/0607105\|s2cid=1750944}}
2016 \|Stephen Brookes and Peter W. O'Hearn \|for their invention of Concurrent Separation Logic \|2007,{{cite journal\|last1=Brookes\|first1=Stephen\|title=A Semantics for Concurrent Separation Logic\|journal=Theoretical Computer Science\|date=2007\|volume=375\|issue=1–3\|pages=227–270\|doi=10.1016/j.tcs.2006.12.034\|url=https://www.cs.cmu.edu/~brookes/papers/seplogicrevisedfinal.pdf}} 2007{{cite journal\|last1=O'Hearn\|first1=Peter\|title=Resources, Concurrency and Local Reasoning\|journal=Theoretical Computer Science\|date=2007\|volume=375\|issue=1–3\|pages=271–307\|doi=10.1016/j.tcs.2006.12.035\|url=http://www.cs.ucl.ac.uk/staff/p.ohearn/papers/concurrency.pdf\|doi-access=free}}
2017{{cite web\|title=2017 Gödel Prize\|url=https://www.eatcs.org/index.php/component/content/article/1-news/2450-2017-godel-prize\|website=European Association for Theoretical Computer Science\|publisher=EATCS\|access-date=29 March 2017}} \|Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith \|for the invention of differential privacy \|2006{{cite conference \|title=Calibrating Noise to Sensitivity in Private Data Analysis \|first1=Cynthia \|last1=Dwork \|first2=Frank \|last2= McSherry \|first3=Kobbi \|last3=Nissim \|first4=Adam \|last4=Smith\| year=2006 \|conference=Theory of Cryptography (TCC)\| editor1-last = Halevi\| editor1-first = Shai\| editor2-last=Rabin\| editor2-first=Tal\|series=Lecture Notes in Computer Science\|volume= 3876 \|publisher= Springer-Verlag \|pages=265–284 \|isbn=978-3-540-32731-8 \|doi=10.1007/11681878_14\|doi-access=free }}
2018{{cite web\|title=2018 Gödel Prize citation\|url=http://eatcs.org/index.php/component/content/article/1-news/2670-2018-godel-prize}} \| Oded Regev \|for introducing the learning with errors problem \|2009{{cite journal\|last1=Regev\|first1=Oded\|title=On lattices, learning with errors, random linear codes, and cryptography\|journal=Journal of the ACM\|volume=56\|issue=6\|pages=1–40\|doi=10.1145/1568318.1568324\|year=2009\|citeseerx=10.1.1.215.3543\|s2cid=207156623}}
2019{{cite web\|title=2019 Gödel Prize citation\|url=http://eatcs.org/index.php/component/content/article/1-news/2807-2019-03-12-20-31-09}} \| Irit Dinur \|for her new proof of the PCP theorem by gap amplification \|2007{{cite journal\|last1=Dinur\|first1=Irit\|title=The PCP theorem by gap amplification\|journal=Journal of the ACM\|volume=54\|issue=3\|pages=12–es\|url=https://dl.acm.org/citation.cfm?id=1236459\|year=2007\|doi=10.1145/1236457.1236459\|s2cid=53244523}}
2020{{cite web\|title=2020 Gödel Prize citation\|url=http://eatcs.org/index.php/component/content/article/1-news/2850-2020-03-31-12-11-16}} \| Robin Moser and Gábor Tardos \| for their constructive proof of the Lovász local lemma \|2010{{cite journal\|journal=Journal of the ACM\|title=A constructive proof of the general Lovász Local Lemma\|volume=57\|issue=2\|year=2010\|issn=0004-5411\|doi=10.1145/1667053}}
2021{{cite web\|title=2021 Gödel Prize citation\|url=https://eatcs.org/index.php/component/content/article/1-news/2885-2021-05-07-21-20-13}} \| 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{{cite journal \| last=Bulatov \| first=Andrei A. \| title=The complexity of the counting constraint satisfaction problem \| journal=Journal of the ACM \| publisher=Association for Computing Machinery \| volume=60 \| issue=5 \| year=2013 \| issn=0004-5411 \| doi=10.1145/2528400 \| pages=1–41\| s2cid=8964233 }} 2013{{cite journal \| last1=Dyer \| first1=Martin \| last2=Richerby \| first2=David \| title=An Effective Dichotomy for the Counting Constraint Satisfaction Problem \| journal=SIAM Journal on Computing \| publisher=Society for Industrial & Applied Mathematics (SIAM) \| volume=42 \| issue=3 \| year=2013 \| issn=0097-5397 \| doi=10.1137/100811258 \| pages=1245–1274\| arxiv=1003.3879 \| s2cid=1247279 }} 2017{{cite journal \| last1=Cai \| first1=Jin-Yi \| last2=Chen \| first2=Xi \| title=Complexity of Counting CSP with Complex Weights \| journal=Journal of the ACM \| publisher=Association for Computing Machinery \| volume=64 \| issue=3 \| date=2017-06-22 \| issn=0004-5411 \| doi=10.1145/2822891 \| pages=1–39\| arxiv=1111.2384 \| s2cid=1053684 }}
2022{{Cite web \|title= 2022 Gödel Prize citation \|work=EATCS \|url=https://eatcs.org/index.php/component/content/article/1-news/2917-2022-05-21-20-13-45 \|last1=Chita \|first1=Efi }} \|Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan \|for their transformative contributions to cryptography by constructing efficient fully homomorphic encryption (FHE) schemes \|2014,{{Cite journal \|last1=Brakerski \|first1=Zvika \|last2=Vaikuntanathan \|first2=Vinod \|date=January 2014 \|title=Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$ \|url=http://dx.doi.org/10.1137/120868669 \|journal=SIAM Journal on Computing \|volume=43 \|issue=2 \|pages=831–871 \|doi=10.1137/120868669 \|hdl=1721.1/115488 \|s2cid=8831240 \|issn=0097-5397\|hdl-access=free }} 2014{{Cite book \|last1=Brakerski \|first1=Zvika \|last2=Gentry \|first2=Craig \|last3=Vaikuntanathan \|first3=Vinod \|title=Proceedings of the 3rd Innovations in Theoretical Computer Science Conference \|chapter=(Leveled) fully homomorphic encryption without bootstrapping \|date=2012 \|chapter-url=http://dx.doi.org/10.1145/2090236.2090262 \|pages=309–325 \|location=New York, New York, USA \|publisher=ACM Press \|doi=10.1145/2090236.2090262\|isbn=9781450311151 \|s2cid=2602543 }}
2023{{Cite web \|title= 2023 Gödel Prize citation \|work=EATCS \|url=https://eatcs.org/index.php/component/content/article/1-news/2945-2023-05-18-18-41-48 \|last1=Chita \|first1=Efi }} \|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, {{Cite journal \| last1 = Fiorini \| first1 = Samuel \| last2 = Massar \| first2 = Serge \| last3 = Pokutta \| first3 = Sebastian \| last4 = Tiwary \| first4 = Hans Raj \| last5 = de Wolf \| first5 = Ronald \| title = Exponential Lower Bounds for Polytopes in Combinatorial Optimization \| journal = Journal of the ACM \| volume = 62 \| issue = 2 \| pages = 17:1–17:23 \| date = 2015 \| doi = 10.1145/2716307 \| s2cid = 7372000 \| url = https://doi.org/10.1145/2716307 \| arxiv = 1111.0837 }} 2017 {{Cite journal \| last = Rothvoss \| first = Thomas \| title = The Matching Polytope has Exponential Extension Complexity \| journal = Journal of the ACM \| volume = 64 \| issue = 6 \| pages = 41:1–41:19 \| date = 2017 \| doi = 10.1145/3127497 \| arxiv = 1311.2369 \| s2cid = 47045361 \| url = https://doi.org/10.1145/3127497 }}
2024{{Cite web \|title=2024 Gödel Prize citation \|url=https://eatcs.org/index.php/component/content/article/1-news/2982-2024-05-13-10-59-08}} \|Ryan Williams \|for his work on circuit lower bounds and the “algorithms to lower bounds” paradigm \|2011{{Cite book \|last=Williams \|first=Ryan \|chapter=Non-uniform ACC Circuit Lower Bounds \|date=June 2011 \|title=2011 IEEE 26th Annual Conference on Computational Complexity \|chapter-url=http://dx.doi.org/10.1109/ccc.2011.36 \|pages=115–125 \|publisher=IEEE \|doi=10.1109/ccc.2011.36\|isbn=978-1-4577-0179-5 }}

Winning papers

Notes

References

[http://www.sigact.org/prizes/g%C3%B6del.html Prize website with list of winners]

Category:Theoretical computer science

Category:Computer science awards

Category:Awards established in 1993

Category:Annual events

class="wikitable sortable" !Year !width=40% class="unsortable"\| Name(s) !width=45% class="unsortable"\| Notes !Publication year
valign="top" \|1993	László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran, and Charles Rackoff	for the development of interactive proof systems	1988,{{Citation \| last1=Babai \| first1=László \| last2=Moran \| first2=Shlomo \| title=Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class \| url=http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC01/AMgames-Babai-Moran.pdf \| year=1988 \| journal=Journal of Computer and System Sciences \| issn=0022-0000 \| volume=36 \| issue=2 \| pages=254–276 \| doi=10.1016/0022-0000(88)90028-1\| doi-access=free }} 1989{{Citation \| last1=Goldwasser \| first1=S. \| last2=Micali \| first2=S. \| last3=Rackoff \| first3=C. \| title=The knowledge complexity of interactive proof systems \| url=http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC02/GMR89.pdf \| year=1989 \| journal=SIAM Journal on Computing \| issn=1095-7111 \| volume=18 \| issue=1 \| pages=186–208 \| doi=10.1137/0218012\| citeseerx=10.1.1.397.4002 }}
valign="top" \|1994	Johan Håstad	for an exponential lower bound on the size of constant-depth Boolean circuits (for the parity function).	1989{{Citation \| last1=Håstad \| first1=Johan \| series=Advances in Computing Research \| volume=5 \| title=Randomness and Computation \| editor-first=Silvio \| editor-last=Micali \| chapter-url=http://reference.kfupm.edu.sa/content/a/l/almost_optimal_lower_bounds_for_small_de_134215.pdf \| publisher=JAI Press \| year=1989 \| chapter=Almost Optimal Lower Bounds for Small Depth Circuits \| pages=6–20 \| isbn=978-0-89232-896-3 \| url-status=dead \| archive-url=https://web.archive.org/web/20120222163102/http://reference.kfupm.edu.sa/content/a/l/almost_optimal_lower_bounds_for_small_de_134215.pdf \| archive-date=2012-02-22 }}
valign=top \|1995	Neil Immerman and Róbert Szelepcsényi	for the Immerman–Szelepcsényi theorem regarding nondeterministic space complexity	1988,{{Citation \| last1=Immerman \| first1=Neil \| author1-link=Neil Immerman \| title=Nondeterministic space is closed under complementation \| url=http://www.cs.umass.edu/~immerman/pub/space.pdf \| year=1988 \| journal=SIAM Journal on Computing \| issn=1095-7111 \| volume=17 \| issue=5 \| pages=935–938 \| doi=10.1137/0217058\| citeseerx=10.1.1.54.5941 }} 1988{{Citation \| last1=Szelepcsényi \| first1=R. \| title=The method of forced enumeration for nondeterministic automata \| year=1988 \| journal=Acta Informatica \| volume=26 \| issue=3 \| pages=279–284 \| doi=10.1007/BF00299636\| hdl=10338.dmlcz/120489 \| s2cid=10838178 \| url=http://dml.cz/bitstream/handle/10338.dmlcz/120489/ActaOstrav_03-1995-1_10.pdf }}
valign="top" \|1996	Mark Jerrum and Alistair Sinclair	for work on Markov chains and the approximation of the permanent of a matrix	1989,{{Citation \| last1=Sinclair \| first1=A. \| last2=Jerrum \| first2=M. \| title=Approximate counting, uniform generation and rapidly mixing Markov chains \| year=1989 \| journal=Information and Computation \| issn=0890-5401 \| volume=82 \| issue=1 \| pages=93–133 \| doi=10.1016/0890-5401(89)90067-9\| doi-access=free }} 1989{{Citation \| last1=Jerrum \| first1=M. \| last2=Sinclair \| first2=Alistair \| title=Approximating the permanent \| year=1989 \| journal=SIAM Journal on Computing \| issn=1095-7111 \| volume=18 \| issue=6 \| pages=1149–1178 \| doi=10.1137/0218077\| citeseerx=10.1.1.431.4190 }}
valign="top" \|1997	Joseph Halpern and Yoram Moses	for defining a formal notion of "knowledge" in distributed environments	1990{{Citation \| last1=Halpern \| first1=Joseph \| author-link1=Joseph Halpern \| last2=Moses \| first2=Yoram \| author-link2=Yoram Moses \| title=Knowledge and common knowledge in a distributed environment \| journal=Journal of the ACM \| volume=37 \| year=1990 \| pages=549–587 \| url=https://www.cs.cornell.edu/home/halpern/papers/common_knowledge.pdf \| doi=10.1145/79147.79161 \| issue=3 \| arxiv=cs/0006009\| s2cid=52151232 }}
valign="top" \|1998	Seinosuke Toda	for Toda's theorem, which showed a connection between counting solutions (PP) and alternation of quantifiers (PH)	1991{{Citation \| last1=Toda \| first1=Seinosuke \| title=PP is as hard as the polynomial-time hierarchy \| url=http://faculty.cs.tamu.edu/chen/courses/637/2008/pres/korben.pdf \| year=1991 \| journal=SIAM Journal on Computing \| issn=1095-7111 \| volume=20 \| issue=5 \| pages=865–877 \| doi=10.1137/0220053 \| citeseerx=10.1.1.121.1246 \| access-date=2010-06-08 \| archive-date=2016-03-03 \| archive-url=https://web.archive.org/web/20160303170125/http://faculty.cs.tamu.edu/chen/courses/637/2008/pres/korben.pdf \| url-status=dead }}
valign="top" \|1999	Peter Shor	for Shor's algorithm for factoring numbers in polynomial time on a quantum computer	1997{{Citation \| last1=Shor \| first1=Peter W. \| title=Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer \| year=1997 \| journal=SIAM Journal on Computing \| issn=1095-7111 \| volume=26 \| issue=5 \| pages=1484–1509 \| doi=10.1137/S0097539795293172 \| arxiv=quant-ph/9508027 \| s2cid=2337707 }}
valign="top" \|2000	Moshe Y. Vardi and Pierre Wolper	for work on temporal logic with finite automata	1994{{Citation \| last1=Vardi \| first1=Moshe Y. \| last2=Wolper \| first2=Pierre \| title=Reasoning about infinite computations \| url=http://reference.kfupm.edu.sa/content/r/e/reasoning_about_infinite_computations__102167.pdf \| year=1994 \| journal=Information and Computation \| issn=0890-5401 \| volume=115 \| issue=1 \| pages=1–37 \| doi=10.1006/inco.1994.1092 \| url-status=dead \| archive-url=https://web.archive.org/web/20110825210914/http://reference.kfupm.edu.sa/content/r/e/reasoning_about_infinite_computations__102167.pdf \| archive-date=2011-08-25 }}
valign="top" \|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,{{Citation \| last1=Feige \| first1=Uriel \| last2=Goldwasser \| first2=Shafi \| last3=Lovász \| first3=Laszlo \| last4=Safra \| first4=Shmuel \| last5=Szegedy \| first5=Mario \| title=Interactive proofs and the hardness of approximating cliques \| url=http://groups.csail.mit.edu/cis/pubs/shafi/1996-jacm.pdf \| year=1996 \| journal=Journal of the ACM \| issn=0004-5411 \| volume=43 \| issue=2 \| pages=268–292 \| doi=10.1145/226643.226652\| doi-access=free }} 1998,{{Citation \| last1=Arora \| first1=Sanjeev \| last2=Safra \| first2=Shmuel \| title=Probabilistic checking of proofs: a new characterization of NP \| url=http://www.cs.umd.edu/~gasarch/pcp/AS.pdf \| year=1998 \| journal=Journal of the ACM \| issn=0004-5411 \| volume=45 \| issue=1 \| pages=70–122 \| doi=10.1145/273865.273901 \| s2cid=751563 \| url-status=dead \| archive-url=https://web.archive.org/web/20110610101051/http://www.cs.umd.edu/~gasarch/pcp/AS.pdf \| archive-date=2011-06-10 }} 1998{{Citation \| last1=Arora \| first1=Sanjeev \| last2=Lund \| first2=Carsten \| last3=Motwani \| first3=Rajeev \| last4=Sudan \| first4=Madhu \| last5=Szegedy \| first5=Mario \| title=Proof verification and the hardness of approximation problems \| url=https://www.cs.umd.edu/~gasarch/pcp/ALMSS.pdf \| year=1998 \| journal=Journal of the ACM \| issn=0004-5411 \| volume=45 \| issue=3 \| pages=501–555 \| doi=10.1145/278298.278306 \| url-status=dead \| archive-url=https://web.archive.org/web/20110610101241/https://www.cs.umd.edu/~gasarch/pcp/ALMSS.pdf \| archive-date=2011-06-10 \| citeseerx=10.1.1.145.4652 \| s2cid=8561542 }}
valign="top" \|2002	Géraud Sénizergues	for proving that equivalence of deterministic pushdown automata is decidable	2001{{Citation \| last1=Sénizergues \| first1=Géraud \| title=L(A) = L(B)? decidability results from complete formal systems \| year=2001 \| journal=Theor. Comput. Sci. \| issn=0304-3975 \| volume=251 \| issue=1 \| pages=1–166 \| doi=10.1016/S0304-3975(00)00285-1\| doi-access= }}
valign="top" \|2003	Yoav Freund and Robert Schapire	for the AdaBoost algorithm in machine learning	1997{{Citation \| last1=Freund \| first1=Y. \| last2=Schapire \| first2=R.E. \| title=A decision-theoretic generalization of on-line learning and an application to boosting \| url=http://www-ai.cs.tu-dortmund.de/LEHRE/PG/PG445/literatur/freund_schapire_97a.pdf \| year=1997 \| journal=Journal of Computer and System Sciences \| issn=1090-2724 \| volume=55 \| issue=1 \| pages=119–139 \| doi=10.1006/jcss.1997.1504}}
valign="top" \|2004	Maurice Herlihy, Michael Saks, Nir Shavit and Fotios Zaharoglou	for applications of topology to the theory of distributed computing	1999,{{Citation \| last1=Herlihy \| first1=Maurice \| author-link1=Maurice Herlihy \| last2=Shavit \| first2=Nir \| author-link2=Nir Shavit \| title=The topological structure of asynchronous computability \| journal=Journal of the ACM \| volume=46 \| year=1999 \| pages=858–923 \| doi=10.1145/331524.331529 \| url=http://www.cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf \| issue=6 \| citeseerx=10.1.1.78.1455 \| s2cid=5797174 }}. [http://www.cs.brown.edu/~mph/finland.pdf Gödel prize lecture] 2000{{Citation \| title=Wait-free k-set agreement is impossible: The topology of public knowledge \| last1=Saks \| first1=Michael \| author-link1=Michael Saks (mathematician) \| last2=Zaharoglou \| first2=Fotios \| author-link2=Fotios Zaharoglou \| journal=SIAM Journal on Computing \| volume=29 \| year=2000 \| pages=1449–1483 \| doi=10.1137/S0097539796307698 \| issue=5 }}
valign="top" \|2005	Noga Alon, Yossi Matias and Mario Szegedy	for their foundational contribution to streaming algorithms	1999{{Citation \| last1=Alon \| first1=Noga \| author1-link=Noga Alon \| last2=Matias \| first2=Yossi \| last3=Szegedy \| first3=Mario \| journal=Journal of Computer and System Sciences \| url=http://www.math.tau.ac.il/~noga/PDFS/amsz4.pdf \| year=1999 \| title=The space complexity of approximating the frequency moments \| volume=58 \| issue=1 \| pages=137–147 \| doi=10.1006/jcss.1997.1545}}. First presented at the Symposium on Theory of Computing (STOC) in 1996.
valign="top" \|2006	Manindra Agrawal, Neeraj Kayal, Nitin Saxena	for the AKS primality test	2004{{Citation \| last1=Agrawal \| first1=M. \| last2=Kayal \| first2=N. \| last3=Saxena \| first3=N. \| title=PRIMES is in P \| year=2004 \| journal=Annals of Mathematics \| issn=0003-486X \| volume=160 \| pages=781–793 \| doi=10.4007/annals.2004.160.781 \| issue=2 \| doi-access=free }}
valign="top" \|2007	Alexander Razborov, Steven Rudich	for natural proofs	1997{{Citation \| last1=Razborov \| first1=Alexander A. \| last2=Rudich \| first2=Steven \| title=Natural proofs \| id={{ECCC\|1994\|94\|010}} \| year=1997 \| journal=Journal of Computer and System Sciences \| issn=0022-0000 \| volume=55 \| issue=1 \| pages=24–35 \| doi=10.1006/jcss.1997.1494\| doi-access=free }}
valign="top" \|2008	Daniel Spielman, Shang-Hua Teng	for smoothed analysis of algorithms	2004{{Citation \| last1=Spielman \| first1=Daniel A. \| last2=Teng \| first2=Shang-Hua \| author2-link=Shanghua Teng \| title=Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time \| year=2004 \| journal=J. ACM \| issn=0004-5411 \| volume=51 \| issue=3 \| pages=385–463 \| doi=10.1145/990308.990310 \| arxiv=math/0212413 }}
valign="top" \|2009	Omer Reingold, Salil Vadhan, Avi Wigderson	for zig-zag product of graphs and undirected connectivity in log space	2002,{{Citation \| last1=Reingold \| first1=Omer \| last2=Vadhan \| first2=Salil \| last3=Wigderson \| first3=Avi \| title=Entropy waves, the zig-zag graph product, and new constant-degree expanders \| mr=1888797 \| year=2002 \| journal=Annals of Mathematics \| issn=0003-486X \| volume=155 \| issue=1 \| pages=157–187 \| doi=10.2307/3062153 \| jstor=3062153 \| citeseerx=10.1.1.236.8669 \| s2cid=120739405 }} 2008{{Citation \| last1=Reingold \| first1=Omer \| title=Undirected connectivity in log-space \| url=http://www.weizmann.ac.il/mathusers/reingold/publications/sl.ps \| year=2008 \| journal=J. ACM \| issn=0004-5411 \| volume=55 \| issue=4 \| pages=1–24 \| doi=10.1145/1391289.1391291 \| s2cid=207168478 }}{{dead link\|date=December 2017 \|bot=InternetArchiveBot \|fix-attempted=yes }}
valign="top" \|2010	Sanjeev Arora, Joseph S. B. Mitchell	for their concurrent discovery of a polynomial-time approximation scheme for the Euclidean Travelling Salesman Problem	1998,{{Citation \| last1=Arora \| first1=Sanjeev \| author1-link=Sanjeev Arora \| title=Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems \| doi=10.1145/290179.290180 \| year=1998 \| journal=Journal of the ACM \| issn=0004-5411 \| volume=45 \| issue=5 \| pages=753–782\| citeseerx=10.1.1.23.6765 \| s2cid=3023351 }} 1999{{Citation \| last1=Mitchell \| first1=Joseph S. B. \| author-link=Joseph S. B. Mitchell \| title=Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems \| doi=10.1137/S0097539796309764 \| year=1999 \| journal=SIAM Journal on Computing \| issn=1095-7111 \| volume=28 \| issue=4 \| pages=1298–1309}}
valign="top" \|2011	Johan Håstad	for proving optimal inapproximability results for various combinatorial problems	2001{{Citation \| last1=Håstad \| first1=Johan \| author1-link=Johan Håstad \| title=Some optimal inapproximability results \| doi=10.1145/502090.502098 \| year=2001 \| journal=Journal of the ACM \| issn=0004-5411 \| volume=48 \| issue=4 \| pages=798–859 \| url=http://www.csc.kth.se/~johanh/optimalinap.pdf\| citeseerx=10.1.1.638.2808 \| s2cid=5120748 }}
valign="top" \|2012	Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden and Éva Tardos	for laying the foundations of algorithmic game theory{{cite news\|title=Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory\|url=http://www.acm.org/press-room/news-releases/2012/goedel-prize-2012\|access-date=16 May 2012\|date=16 May 2012\|url-status=dead\|archive-url=https://web.archive.org/web/20130718154540/http://www.acm.org/press-room/news-releases/2012/goedel-prize-2012\|archive-date=18 July 2013}}	2009,{{cite journal\|last=Koutsoupias\|first=Elias\|author2=Papadimitriou, Christos\|title=Worst-case equilibria\|journal=Computer Science Review\|year=2009\|volume=3\|issue=2\|pages=65–69\|doi=10.1016/j.cosrev.2009.04.003}} 2002,{{cite journal\|last=Roughgarden\|first=Tim\|author2=Tardos, Éva\|title=How bad is selfish routing?\|journal=Journal of the ACM\|year=2002\|volume=49\|issue=2\|pages=236–259\|doi=10.1145/506147.506153\|citeseerx=10.1.1.147.1081\|s2cid=207638789}} 2001{{cite journal\|last=Nisan\|first=Noam\|author2=Ronen, Amir\|title=Algorithmic Mechanism Design\|journal=Games and Economic Behavior\|year=2001\|volume=35\|issue=1–2\|pages=166–196\|doi=10.1006/game.1999.0790\|citeseerx=10.1.1.21.1731}}
valign="top" \|2013	Dan Boneh, Matthew K. Franklin, and Antoine Joux	for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography[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] {{webarchive\|url=https://web.archive.org/web/20130601191333/http://www.acm.org/press-room/news-releases/2013/goedel-prize-13 \|date=2013-06-01 }}, Association for Computing Machinery, May 29, 2013.	2003,{{cite journal \| last1 = Boneh \| first1 = Dan \| last2 = Franklin \| first2 = Matthew \| doi = 10.1137/S0097539701398521 \| issue = 3 \| journal = SIAM Journal on Computing \| mr = 2001745 \| pages = 586–615 \| title = Identity-based encryption from the Weil pairing \| volume = 32 \| year = 2003\| citeseerx = 10.1.1.66.1131 }} 2004{{cite journal \| last = Joux \| first = Antoine \| doi = 10.1007/s00145-004-0312-y \| issue = 4 \| journal = Journal of Cryptology \| mr = 2090557 \| pages = 263–276 \| title = A one round protocol for tripartite Diffie-Hellman \| volume = 17 \| year = 2004\| s2cid = 3350730 \| doi-access = free }}
valign="top" \|2014	Ronald Fagin, {{Interlanguage link\|Amnon Lotem\|fr}}, and Moni Naor	for Optimal Aggregation Algorithms for middleware[https://eatcs.org/index.php/component/content/article/1-news/1908-goedel-prize-2014 Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources], Association for Computing Machinery, April 30, 2014.	2003,{{cite journal \| last1 = Fagin \| first1 = Ronald \| last2 = Lotem \| first2 = Amnon \| last3 = Naor \| first3 = Moni \| doi = 10.1016/S0022-0000(03)00026-6 \| issue = 4 \| journal = Journal of Computer and System Sciences \| pages = 614–656 \| title = Optimal aggregation algorithms for middleware \| volume = 66 \| year = 2003\| arxiv = cs/0204046 }}
valign="top" \|2015	Daniel Spielman, Shang-Hua Teng	for their series of papers on nearly-linear-time Laplacian solvers[http://www.sigact.org/Prizes/Godel/citation2015.pdf 2015 Gödel Prize announcement] {{Webarchive\|url=https://web.archive.org/web/20171209021752/http://www.sigact.org/Prizes/Godel/citation2015.pdf \|date=2017-12-09 }} by Association for Computing Machinery.	2011{{cite journal\|last1=Spielman\|first1=Daniel A.\|last2=Teng\|first2=Shang-Hua\|title=Spectral Sparsification of Graphs\|journal=SIAM Journal on Computing\|volume=40\|issue=4\|year=2011\|pages=981–1025\|issn=0097-5397\|doi=10.1137/08074489X\|arxiv=0808.4134\|s2cid=9646279}} 2013{{cite journal\|last1=Spielman\|first1=Daniel A.\|last2=Teng\|first2=Shang-Hua\|title=A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning\|journal=SIAM Journal on Computing\|volume=42\|issue=1\|year=2013\|pages=1–26\|issn=0097-5397\|doi=10.1137/080744888\|arxiv=0809.3232\|s2cid=9151077}} 2014{{cite journal\|last1=Spielman\|first1=Daniel A.\|last2=Teng\|first2=Shang-Hua\|title=Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems\|journal=SIAM Journal on Matrix Analysis and Applications\|volume=35\|issue=3\|year=2014\|pages=835–885\|issn=0895-4798\|doi=10.1137/090771430\|arxiv=cs/0607105\|s2cid=1750944}}
2016 \|Stephen Brookes and Peter W. O'Hearn \|for their invention of Concurrent Separation Logic \|2007,{{cite journal\|last1=Brookes\|first1=Stephen\|title=A Semantics for Concurrent Separation Logic\|journal=Theoretical Computer Science\|date=2007\|volume=375\|issue=1–3\|pages=227–270\|doi=10.1016/j.tcs.2006.12.034\|url=https://www.cs.cmu.edu/~brookes/papers/seplogicrevisedfinal.pdf}} 2007{{cite journal\|last1=O'Hearn\|first1=Peter\|title=Resources, Concurrency and Local Reasoning\|journal=Theoretical Computer Science\|date=2007\|volume=375\|issue=1–3\|pages=271–307\|doi=10.1016/j.tcs.2006.12.035\|url=http://www.cs.ucl.ac.uk/staff/p.ohearn/papers/concurrency.pdf\|doi-access=free}}
2017{{cite web\|title=2017 Gödel Prize\|url=https://www.eatcs.org/index.php/component/content/article/1-news/2450-2017-godel-prize\|website=European Association for Theoretical Computer Science\|publisher=EATCS\|access-date=29 March 2017}} \|Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith \|for the invention of differential privacy \|2006{{cite conference \|title=Calibrating Noise to Sensitivity in Private Data Analysis \|first1=Cynthia \|last1=Dwork \|first2=Frank \|last2= McSherry \|first3=Kobbi \|last3=Nissim \|first4=Adam \|last4=Smith\| year=2006 \|conference=Theory of Cryptography (TCC)\| editor1-last = Halevi\| editor1-first = Shai\| editor2-last=Rabin\| editor2-first=Tal\|series=Lecture Notes in Computer Science\|volume= 3876 \|publisher= Springer-Verlag \|pages=265–284 \|isbn=978-3-540-32731-8 \|doi=10.1007/11681878_14\|doi-access=free }}
2018{{cite web\|title=2018 Gödel Prize citation\|url=http://eatcs.org/index.php/component/content/article/1-news/2670-2018-godel-prize}} \| Oded Regev \|for introducing the learning with errors problem \|2009{{cite journal\|last1=Regev\|first1=Oded\|title=On lattices, learning with errors, random linear codes, and cryptography\|journal=Journal of the ACM\|volume=56\|issue=6\|pages=1–40\|doi=10.1145/1568318.1568324\|year=2009\|citeseerx=10.1.1.215.3543\|s2cid=207156623}}
2019{{cite web\|title=2019 Gödel Prize citation\|url=http://eatcs.org/index.php/component/content/article/1-news/2807-2019-03-12-20-31-09}} \| Irit Dinur \|for her new proof of the PCP theorem by gap amplification \|2007{{cite journal\|last1=Dinur\|first1=Irit\|title=The PCP theorem by gap amplification\|journal=Journal of the ACM\|volume=54\|issue=3\|pages=12–es\|url=https://dl.acm.org/citation.cfm?id=1236459\|year=2007\|doi=10.1145/1236457.1236459\|s2cid=53244523}}
2020{{cite web\|title=2020 Gödel Prize citation\|url=http://eatcs.org/index.php/component/content/article/1-news/2850-2020-03-31-12-11-16}} \| Robin Moser and Gábor Tardos \| for their constructive proof of the Lovász local lemma \|2010{{cite journal\|journal=Journal of the ACM\|title=A constructive proof of the general Lovász Local Lemma\|volume=57\|issue=2\|year=2010\|issn=0004-5411\|doi=10.1145/1667053}}
2021{{cite web\|title=2021 Gödel Prize citation\|url=https://eatcs.org/index.php/component/content/article/1-news/2885-2021-05-07-21-20-13}} \| 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{{cite journal \| last=Bulatov \| first=Andrei A. \| title=The complexity of the counting constraint satisfaction problem \| journal=Journal of the ACM \| publisher=Association for Computing Machinery \| volume=60 \| issue=5 \| year=2013 \| issn=0004-5411 \| doi=10.1145/2528400 \| pages=1–41\| s2cid=8964233 }} 2013{{cite journal \| last1=Dyer \| first1=Martin \| last2=Richerby \| first2=David \| title=An Effective Dichotomy for the Counting Constraint Satisfaction Problem \| journal=SIAM Journal on Computing \| publisher=Society for Industrial & Applied Mathematics (SIAM) \| volume=42 \| issue=3 \| year=2013 \| issn=0097-5397 \| doi=10.1137/100811258 \| pages=1245–1274\| arxiv=1003.3879 \| s2cid=1247279 }} 2017{{cite journal \| last1=Cai \| first1=Jin-Yi \| last2=Chen \| first2=Xi \| title=Complexity of Counting CSP with Complex Weights \| journal=Journal of the ACM \| publisher=Association for Computing Machinery \| volume=64 \| issue=3 \| date=2017-06-22 \| issn=0004-5411 \| doi=10.1145/2822891 \| pages=1–39\| arxiv=1111.2384 \| s2cid=1053684 }}
2022{{Cite web \|title= 2022 Gödel Prize citation \|work=EATCS \|url=https://eatcs.org/index.php/component/content/article/1-news/2917-2022-05-21-20-13-45 \|last1=Chita \|first1=Efi }} \|Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan \|for their transformative contributions to cryptography by constructing efficient fully homomorphic encryption (FHE) schemes \|2014,{{Cite journal \|last1=Brakerski \|first1=Zvika \|last2=Vaikuntanathan \|first2=Vinod \|date=January 2014 \|title=Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$ \|url=http://dx.doi.org/10.1137/120868669 \|journal=SIAM Journal on Computing \|volume=43 \|issue=2 \|pages=831–871 \|doi=10.1137/120868669 \|hdl=1721.1/115488 \|s2cid=8831240 \|issn=0097-5397\|hdl-access=free }} 2014{{Cite book \|last1=Brakerski \|first1=Zvika \|last2=Gentry \|first2=Craig \|last3=Vaikuntanathan \|first3=Vinod \|title=Proceedings of the 3rd Innovations in Theoretical Computer Science Conference \|chapter=(Leveled) fully homomorphic encryption without bootstrapping \|date=2012 \|chapter-url=http://dx.doi.org/10.1145/2090236.2090262 \|pages=309–325 \|location=New York, New York, USA \|publisher=ACM Press \|doi=10.1145/2090236.2090262\|isbn=9781450311151 \|s2cid=2602543 }}
2023{{Cite web \|title= 2023 Gödel Prize citation \|work=EATCS \|url=https://eatcs.org/index.php/component/content/article/1-news/2945-2023-05-18-18-41-48 \|last1=Chita \|first1=Efi }} \|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, {{Cite journal \| last1 = Fiorini \| first1 = Samuel \| last2 = Massar \| first2 = Serge \| last3 = Pokutta \| first3 = Sebastian \| last4 = Tiwary \| first4 = Hans Raj \| last5 = de Wolf \| first5 = Ronald \| title = Exponential Lower Bounds for Polytopes in Combinatorial Optimization \| journal = Journal of the ACM \| volume = 62 \| issue = 2 \| pages = 17:1–17:23 \| date = 2015 \| doi = 10.1145/2716307 \| s2cid = 7372000 \| url = https://doi.org/10.1145/2716307 \| arxiv = 1111.0837 }} 2017 {{Cite journal \| last = Rothvoss \| first = Thomas \| title = The Matching Polytope has Exponential Extension Complexity \| journal = Journal of the ACM \| volume = 64 \| issue = 6 \| pages = 41:1–41:19 \| date = 2017 \| doi = 10.1145/3127497 \| arxiv = 1311.2369 \| s2cid = 47045361 \| url = https://doi.org/10.1145/3127497 }}
2024{{Cite web \|title=2024 Gödel Prize citation \|url=https://eatcs.org/index.php/component/content/article/1-news/2982-2024-05-13-10-59-08}} \|Ryan Williams \|for his work on circuit lower bounds and the “algorithms to lower bounds” paradigm \|2011{{Cite book \|last=Williams \|first=Ryan \|chapter=Non-uniform ACC Circuit Lower Bounds \|date=June 2011 \|title=2011 IEEE 26th Annual Conference on Computational Complexity \|chapter-url=http://dx.doi.org/10.1109/ccc.2011.36 \|pages=115–125 \|publisher=IEEE \|doi=10.1109/ccc.2011.36\|isbn=978-1-4577-0179-5 }}

Gödel Prize

Recipients

Winning papers

See also

Notes

References