Gödel Prize

From Wikipedia, the free encyclopedia

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. 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.

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 temporal logic 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 in machine learning 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 Daniel Spielman, Shanghua Tengfor 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]
2010 Sanjeev Arora, Joseph S. B. Mitchell for their concurrent discovery of a polynomial-time approximation scheme (PTAS) for the Euclidean Travelling Salesman Problem (ETSP) 1998,[paper 25]

1999[paper 26]

2011 Johan Håstad for proving optimal inapproximability result for various combinatorial problems 2001[paper 27]
2012 Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden and Éva Tardos for laying the foundations of algorithmic game theory[1] 2009,[paper 28] 2002,[paper 29] 2001[paper 30]
2013 Dan Boneh, Matthew K. Franklin, and Antoine Joux for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography[2] 2003,[paper 31]

2004[paper 32]

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 
  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 
  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 0-89232-896-7 
  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 
  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 
  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 
  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 
  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 
  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 
  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 
  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 
  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 . 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 . 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 (2): 781–793, doi:10.4007/annals.2004.160.781, ISSN 0003-486X 
  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, ECCC TR94-010 
  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 
  23. ↑ Reingold, Omer; Vadhan, Salil; Wigderson, Avi (2002), "Entropy waves, the zig-zag graph product, and new constant-degree expanders", Annals of Mathematics (Annals of Mathematics) 155 (1): 157–187, doi:10.2307/3062153, ISSN 0003-486X, JSTOR 3062153, MR 1888797 
  24. ↑ Reingold, Omer (2008), "Undirected connectivity in log-space", J. ACM (ACM) 55 (4): 1–24, ISSN 0004-5411 
  25. ↑ Arora, Sanjeev (1998), "Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems", Journal of the ACM (ACM) 45 (5): 753–782, doi:10.1145/290179.290180, ISSN 0004-5411 
  26. ↑ Mitchell, Joseph S. B. (1999), "Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems", SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 28 (4): 1298–1309, doi:10.1137/S0097539796309764, ISSN 1095-7111 
  27. ↑ Håstad, Johan (2001), "Some optimal inapproximability results", Journal of the ACM (ACM) 48: 798–859, doi:10.1145/502090.502098, ISSN 0004-5411 
  28. ↑ Koutsoupias, Elias; Papadimitriou, Christos (2009). "Worst-case equilibria". Computer Science Review 3 (2): 65–69. doi:10.1016/j.cosrev.2009.04.003. 
  29. ↑ Roughgarden, Tim; Tardos, Éva (2002). "How bad is selfish routing?". Journal of the ACM 49 (2): 236–259. doi:10.1145/506147.506153. 
  30. ↑ Nisan, Noam; Ronen, Amir (2001). "Algorithmic Mechanism Design". Games and Economic Behavior 35 (1-2): 166–196. doi:10.1006/game.1999.0790. 
  31. ↑ Boneh, Dan; Franklin, Matthew (2003). "Identity-based encryption from the Weil pairing". SIAM Journal on Computing 32 (3): 586–615. doi:10.1137/S0097539701398521. MR 2001745. 
  32. ↑ Joux, Antoine (2004). "A one round protocol for tripartite Diffie-Hellman". Journal of Cryptology 17 (4): 263–276. doi:10.1007/s00145-004-0312-y. MR 2090557. 

References

  1. ↑ "Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory". 16 May 2012. Retrieved 16 May 2012. 
  2. ↑ ACM 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.
This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.