Gödel Prize
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by 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 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.
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.
Recipients
Winning papers
- ↑ Babai, László; Moran, Shlomo (1988), "Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class" (PDF), 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
- ↑ Goldwasser, S.; Micali, S.; Rackoff, C. (1989), "The knowledge complexity of interactive proof systems" (PDF), SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 18 (1): 186–208, doi:10.1137/0218012, ISSN 1095-7111
- ↑ Håstad, Johan (1989), "Almost Optimal Lower Bounds for Small Depth Circuits", in Micali, Silvio, Randomness and Computation (PDF), Advances in Computing Research 5, JAI Press, pp. 6–20, ISBN 0-89232-896-7
- ↑ Immerman, Neil (1988), "Nondeterministic space is closed under complementation" (PDF), SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 17 (5): 935–938, doi:10.1137/0217058, ISSN 1095-7111
- ↑ 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
- ↑ 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
- ↑ 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
- ↑ Halpern, Joseph; Moses, Yoram (1990), "Knowledge and common knowledge in a distributed environment" (PDF), Journal of the ACM 37 (3): 549–587, doi:10.1145/79147.79161
- ↑ Toda, Seinosuke (1991), "PP is as hard as the polynomial-time hierarchy" (PDF), SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 20 (5): 865–877, doi:10.1137/0220053, ISSN 1095-7111
- ↑ Shor, Peter W. (1997), "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer" (PDF), SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 26 (5): 1484–1509, doi:10.1137/S0097539795293172, ISSN 1095-7111
- ↑ Vardi, Moshe Y.; Wolper, Pierre (1994), "Reasoning about infinite computations" (PDF), Information and Computation (Boston, MA: Academic Press) 115 (1): 1–37, doi:10.1006/inco.1994.1092, ISSN 0890-5401
- ↑ Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996), "Interactive proofs and the hardness of approximating cliques" (PDF), Journal of the ACM (ACM) 43 (2): 268–292, doi:10.1145/226643.226652, ISSN 0004-5411
- ↑ Arora, Sanjeev; Safra, Shmuel (1998), "Probabilistic checking of proofs: a new characterization of NP" (PDF), Journal of the ACM (ACM) 45 (1): 70–122, doi:10.1145/273865.273901, ISSN 0004-5411
- ↑ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), "Proof verification and the hardness of approximation problems" (PDF), Journal of the ACM (ACM) 45 (3): 501–555, doi:10.1145/278298.278306, ISSN 0004-5411
- ↑ 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
- ↑ Freund, Y.; Schapire, R.E. (1997), "A decision-theoretic generalization of on-line learning and an application to boosting" (PDF), Journal of Computer and System Sciences (Elsevier) 55 (1): 119–139, doi:10.1006/jcss.1997.1504, ISSN 1090-2724
- ↑ Herlihy, Maurice; Shavit, Nir (1999), "The topological structure of asynchronous computability" (PDF), Journal of the ACM 46 (6): 858–923, doi:10.1145/331524.331529. Gödel prize lecture
- ↑ 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
- ↑ Alon, Noga; Matias, Yossi; Szegedy, Mario (1999), "The space complexity of approximating the frequency moments" (PDF), 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.
- ↑ Agrawal, M.; Kayal, N.; Saxena, N. (2004), "PRIMES is in P" (PDF), Annals of Mathematics 160 (2): 781–793, doi:10.4007/annals.2004.160.781, ISSN 0003-486X
- ↑ 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
- ↑ Spielman, Daniel A.; Teng, Shang-Hua (2004), "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time" (PDF), J. ACM (ACM) 51 (3): 385–463, doi:10.1145/990308.990310, ISSN 0004-5411
- ↑ Reingold, Omer; Vadhan, Salil; Wigderson, Avi (2002), "Entropy waves, the zig-zag graph product, and new constant-degree expanders" (PDF), Annals of Mathematics (Annals of Mathematics) 155 (1): 157–187, doi:10.2307/3062153, ISSN 0003-486X, JSTOR 3062153, MR 1888797
- ↑ Reingold, Omer (2008), "Undirected connectivity in log-space", J. ACM (ACM) 55 (4): 1–24, doi:10.1145/1391289.1391291, ISSN 0004-5411
- ↑ 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
- ↑ 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
- ↑ Håstad, Johan (2001), "Some optimal inapproximability results" (PDF), Journal of the ACM (ACM) 48: 798–859, doi:10.1145/502090.502098, ISSN 0004-5411
- ↑ Koutsoupias, Elias; Papadimitriou, Christos (2009). "Worst-case equilibria". Computer Science Review 3 (2): 65–69. doi:10.1016/j.cosrev.2009.04.003.
- ↑ Roughgarden, Tim; Tardos, Éva (2002). "How bad is selfish routing?". Journal of the ACM 49 (2): 236–259. doi:10.1145/506147.506153.
- ↑ Nisan, Noam; Ronen, Amir (2001). "Algorithmic Mechanism Design". Games and Economic Behavior 35 (1-2): 166–196. doi:10.1006/game.1999.0790.
- ↑ 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.
- ↑ 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.
- ↑ Fagin, Ronald; Lotem, Amnon; Naor, Moni (2003). "Optimal aggregation algorithms for middleware". Journal of Computer and System Sciences 66 (4): 614–656. doi:10.1016/S0022-0000(03)00026-6.
- ↑ Spielman, Daniel A.; Teng, Shang-Hua (2011). "Spectral Sparsification of Graphs". SIAM Journal on Computing 40 (4): 981–1025. doi:10.1137/08074489X. ISSN 0097-5397.
- ↑ Spielman, Daniel A.; Teng, Shang-Hua (2013). "A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning". SIAM Journal on Computing 42 (1): 1–26. doi:10.1137/080744888. ISSN 0097-5397.
- ↑ Spielman, Daniel A.; Teng, Shang-Hua (2014). "Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems". SIAM Journal on Matrix Analysis and Applications 35 (3): 835–885. doi:10.1137/090771430. ISSN 0895-4798.
References
- ↑ "Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory". 16 May 2012. Retrieved 16 May 2012.
- ↑ 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.
- ↑ Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources, Association for Computing Machinery, April 30, 2014.
- ↑ [http://www.sigact.org/Prizes/Godel/citation2015.pdf 2015 Gödel Prize Association for Computing Machinery announcement.