The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory (ACM SIGACT).

The Gödel Prize has been awarded annually since 1993. It includes an award of $5000. The prize is awarded either at STOC (ACM Symposium on Theory of Computing, one of the main North American conferences in theoretical computer science) or ICALP (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.

[edit] 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[paper 1], 1989[paper 2]
1994	Johan Håstad	for an exponential lower bound on the size of constant-depth Boolean circuits (for the parity function).	1989[paper 3]
1995	Neil Immerman and Róbert Szelepcsényi	for the Immerman-Szelepcsényi theorem regarding nondeterministic space complexity	1988[paper 4], 1988[paper 5]
1996	Mark Jerrum and Alistair Sinclair	for work on Markov chains and the approximation of the permanent	1989[paper 6], 1989[paper 7]
1997	Joseph Halpern and Yoram Moses	for defining a formal notion of "knowledge" in distributed environments	1990[paper 8]
1998	Seinosuke Toda	for Toda's theorem which showed a connection between counting solutions (PP) and alternation of quantifiers (PH)	1991[paper 9]
1999	Peter Shor	for Shor's algorithm for factoring numbers in polynomial time on a quantum computer	1997[paper 10]
2000	Moshe Y. Vardi and Pierre Wolper	for work on model checking with finite automata	1994[paper 11]
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[paper 12], 1998[paper 13], 1998[paper 14]
2002	Géraud Sénizergues	for proving that equivalence of deterministic pushdown automata is decidable	2001[paper 15]
2003	Yoav Freund and Robert Schapire	for the AdaBoost algorithm	1997[paper 16]
2004	Maurice Herlihy, Michael Saks, Nir Shavit and Fotios Zaharoglou	for applications of topology to the theory of distributed computing	1999[paper 17], 2000[paper 18]
2005	Noga Alon, Yossi Matias and Mario Szegedy	for their foundational contribution to streaming algorithms	1999[paper 19]
2006	Manindra Agrawal, Neeraj Kayal, Nitin Saxena	for the AKS primality test	2004[paper 20]
2007	Alexander Razborov, Steven Rudich	for natural proofs	1997[paper 21]
2008	Shanghua Teng, Daniel Spielman	for smoothed analysis of algorithms	2004[paper 22]
2009	Omer Reingold, Salil Vadhan, Avi Wigderson	for zig-zag product of graphs and undirected connectivity in log space	2002[paper 23], 2008[paper 24]

[edit] Winning papers

1. ^ Babai, László; Moran, Shlomo (1988), "Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class", Journal of Computer and System Sciences (Boston, MA: Academic Press) 36 (2): 254–276, doi:10.1016/0022-0000(88)90028-1, ISSN 0022-0000, http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC01/AMgames-Babai-Moran.pdf 
2. ^ Goldwasser, S.; Micali, S.; Rackoff, C. (1989), "The knowledge complexity of interactive proof systems", SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 18 (1): 186–208, doi:10.1137/0218012, ISSN 1095-7111, http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC02/GMR89.pdf 
3. ^ Håstad, Johan (1989), "Almost Optimal Lower Bounds for Small Depth Circuits", in Micali, Silvio, Randomness and Computation, Advances in Computing Research, 5, JAI Press, pp. 6–20, ISBN 0892328967, http://reference.kfupm.edu.sa/content/a/l/almost_optimal_lower_bounds_for_small_de_134215.pdf 
4. ^ Immerman, Neil (1988), "Nondeterministic space is closed under complementation", SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 17 (5): 935–938, doi:10.1137/0217058, ISSN 1095-7111, http://www.cs.umass.edu/~immerman/pub/space.pdf 
5. ^ Szelepcsényi, R. (1988), "The method of forced enumeration for nondeterministic automata", Acta Informatica (Springer-Verlag New York, Inc.) 26 (3): 279–284, doi:10.1007/BF00299636 
6. ^ Sinclair, A.; Jerrum, M. (1989), "Approximate counting, uniform generation and rapidly mixing Markov chains", Information and Computation (Elsevier) 82 (1): 93–133, doi:10.1016/0890-5401(89)90067-9, ISSN 0890-5401 
7. ^ Jerrum, M.; Sinclair, Alistair (1989), "Approximating the permanent", SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 18 (6): 1149–1178, doi:10.1137/0218077, ISSN 1095-7111 
8. ^ Halpern, Joseph; Moses, Yoram (1990), "Knowledge and common knowledge in a distributed environment", Journal of the ACM 37 (3): 549–587, doi:10.1145/79147.79161 
9. ^ Toda, Seinosuke (1991), "PP is as hard as the polynomial-time hierarchy", SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 20 (5): 865–877, doi:10.1137/0220053, ISSN 1095-7111, http://www1.cs.columbia.edu/~homin/dixon/tod91.pdf 
10. ^ Shor, Peter W. (1997), "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 26 (5): 1484–1509, doi:10.1137/S0097539795293172, ISSN 1095-7111, http://physics.princeton.edu/~mcdonald/examples/QM/shor_siamjc_26_1484_97.pdf 
11. ^ Vardi, Moshe Y.; Wolper, Pierre (1994), "Reasoning about infinite computations", Information and Computation (Boston, MA: Academic Press) 115 (1): 1–37, doi:10.1006/inco.1994.1092, ISSN 0890-5401, http://reference.kfupm.edu.sa/content/r/e/reasoning_about_infinite_computations__102167.pdf 
12. ^ Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996), "Interactive proofs and the hardness of approximating cliques", Journal of the ACM (ACM) 43 (2): 268–292, doi:10.1145/226643.226652, ISSN 0004-5411, http://groups.csail.mit.edu/cis/pubs/shafi/1996-jacm.pdf 
13. ^ Arora, Sanjeev; Safra, Shmuel (1998), "Probabilistic checking of proofs: a new characterization of NP", Journal of the ACM (ACM) 45 (1): 70–122, doi:10.1145/273865.273901, ISSN 0004-5411, http://www.cs.umd.edu/~gasarch/pcp/AS.pdf 
14. ^ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), "Proof verification and the hardness of approximation problems", Journal of the ACM (ACM) 45 (3): 501–555, doi:10.1145/278298.278306, ISSN 0004-5411, https://www.cs.umd.edu/~gasarch/pcp/ALMSS.pdf 
15. ^ Sénizergues, Géraud (2001), "L(A) = L(B)? decidability results from complete formal systems", Theor. Comput. Sci. (Essex, UK: Elsevier Science Publishers Ltd.) 251 (1): 1–166, doi:10.1016/S0304-3975(00)00285-1, ISSN 0304-3975 
16. ^ Freund, Y.; Schapire, R.E. (1997), "A decision-theoretic generalization of on-line learning and an application to boosting", Journal of Computer and System Sciences (Elsevier) 55 (1): 119–139, doi:10.1006/jcss.1997.1504, ISSN 1090-2724, http://www-ai.cs.tu-dortmund.de/LEHRE/PG/PG445/literatur/freund_schapire_97a.pdf 
17. ^ Herlihy, Maurice; Shavit, Nir (1999), "The topological structure of asynchronous computation", Journal of the ACM 46 (6): 858–923, doi:10.1145/331524.331529, http://www.cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf . Gödel prize lecture
18. ^ 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 
19. ^ Alon, Noga; Matias, Yossi; Szegedy, Mario (1999), "The space complexity of approximating the frequency moments", Journal of Computer and System Sciences 58 (1): 137–147, doi:10.1006/jcss.1997.1545, http://www.math.tau.ac.il/~noga/PDFS/amsz4.pdf . First presented at the Symposium on Theory of Computing (STOC) in 1996.
20. ^ Agrawal, M.; Kayal, N.; Saxena, N. (2004), "PRIMES is in P", Annals of Mathematics 160: 781–793, doi:10.4007/annals.2004.160.781, ISSN 0003-486X, http://math.berkeley.edu/~coleman/Courses/Fall08/Cryptography/primality_v6.pdf 
21. ^ Razborov, Alexander A.; Rudich, Steven (1997), "Natural proofs", Journal of Computer and System Sciences (Boston, MA: Academic Press) 55 (1): 24–35, doi:10.1006/jcss.1997.1494, ISSN 0022-0000, http://eccc.uni-trier.de/report/1994/010/download 
22. ^ Spielman, Daniel A.; Teng, Shang-Hua (2004), "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time", J. ACM (ACM) 51 (3): 385–463, ISSN 0004-5411, http://eprints.kfupm.edu.sa/65442/1/65442.pdf 
23. ^ 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, doi:10.2307/3062153, MR1888797, ISSN 0003-486X, http://eprints.kfupm.edu.sa/37801/1/37801.pdf 
24. ^ Reingold, Omer (2008), "Undirected connectivity in log-space", J. ACM (ACM) 55 (4): 1–24, ISSN 0004-5411, http://www.weizmann.ac.il/mathusers/reingold/publications/sl.ps 

[edit] References

• Prize website with list of winners