The Gödel Prize for outstanding papers in the area of theoretical computer science is sponsored 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 award is presented annually, with the presentation taking place alternately at the International Colloquium on Automata, Languages, and Programming (ICALP) and the ACM Symposium on Theory of Computing (STOC). The nineteenth prize will be awarded at the 43rd ACM symposium on the Theory of Computing to be held as part of FCRC in San Jose, California, in June 2011. The Prize is named in honor of Kurt Gödel in recognition of his major contributions to mathematical logic and of his interest, discovered in a letter he wrote to John von Neumann shortly before von Neumann’s death, in what has become the famous “P versus NP” question. The Prize includes an award of USD 5000.
AWARD COMMITTEE : 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. The 2011 Award Committee consists of Sanjeev Arora (Princeton), Josep Diaz (Universitat Politecnica de Catalunya), Cynthia Dwork (Microsoft Research), Mogens Nielsen (University of Aarhus), Mike Paterson (University of Warwick) and Eli Upfal (Brown University).
ELIGIBILITY : The last change of rules goes back to the 2005 Prize. The (parametric) rule can be found on websites of both SIGACT and EATCS. The rule for the 2011 Prize is given below and supersedes any different interpretation of the parametric rule. Any research paper or series of papers by a single author or by a team of authors is deemed eligible if
(i) the paper was published in a recognized refereed journal no later than December 10, 2010;
(ii) the main results were not published (in either preliminary or final form) in a journal or conference proceedings before January 1st, 1998.
The research work nominated for the award should be in the area of theoretical computer science. The term “theoretical computer science” is meant to encompass, but is not restricted to, those areas covered by ICALP and STOC. Nominations are encouraged from the broadest spectrum of the theoretical computer science community so as to ensure that potential award winning papers are not overlooked. The Award Committee shall have the ultimate authority to decide whether a particular paper is eligible for the Prize.
NOMINATIONS : Nominations for the award should be submitted by email to the Award Committee Chair : Eli Upfal eli@cs.brown.edu . To be considered, nominations for the 2011 Prize must be received by December 10, 2010. Nominations may be made by any member of the scientific community. It is the duty of the Award Committee to actively solicit nominations. A nomination should contain a brief summary of the technical content of the paper(s) and a brief explanation of its significance. A printable copy of the research paper or papers should accompany the nomination. The nomination must state the date and venue of the first conference or workshop publication or state that no such publication has occurred. The work may be in any language. However, if it is not in English, a more extended summary written in English should be enclosed. Additional recommendations in favor of the nominated work may also be enclosed. To be considered for the award, the paper or series of papers must be recommended by at least two individuals, either in the form of two distinct nominations or one nomination including recommendations from two different people. Those intending to submit a nomination are encouraged to contact the Award Committee Chair by email well in advance. The Award Committee will accept informal proposals of potential nominees, as well as tentative offers to prepare formal nominations. The “Subject” line of all related messages should begin with “Gödel 2011”.
SELECTION PROCESS: Although the Award Committee is encouraged to consult with the theoretical computer science community at large, the Award Committee is solely responsible for the selection of the winner of the award. The Prize may be shared by more than one paper or series of papers, and the Award Committee reserves the right to declare no winner at all. All matters relating to the selection process that are not specified here are left to the discretion of the Award Committee.
PAST WINNERS:
2010: S. Arora. Polynomial-time approximation schemes for Euclidean TSP and other geometric problems, Journal ACM 45(5), (1998), 753-782. J.S.B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems, SIAM J. Computing 28(4), (1999), 1298-1309.
2009: Omer Reingold, Salil Vadhan, and Avi Wigderson, “Entropywaves, the zig-zag graph product, and new constant-degree expanders”, Annals of Mathematics, 155 (2002), 157–187.
Omer Reingold, “Undirected connectivity in log-space”, Journal of the ACM 55
(2008), 1–24.
2008: Daniel A. Spielman and Shang-Hua Teng, “Smoothed analysis of algorithms : Why the simplex algorithm usually takes polynomial time”, Journal of the ACM, 51 (2004), 385–463.
2007: Alexander A. Razborov and Steven Rudich, “Natural Proofs”, Journal of Computer and System Sciences, 55 (1997), 24–35.
2006: Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, “PRIMES is in P”, Annals of
Mathematics, 160 (2004), 1–13.
2005: Noga Alon, Yossi Matias and Mario Szegedy, “The space complexity of approximating
the frequency moments”, Journal of Computer and System Sciences, 58 (1999), 137– 147.
2004: Maurice Herlihy and Nir Shavit, “The Topological Structure of Asynchronous Computation”, Journal of the ACM, 46 (1999), 858–923.
Michael Saks and Fotios Zaharoglou, “Wait-Free k-Set Agreement Is Impossible :
The Topology of Public Knowledge”, SIAM Journal of Computing, 29 (2000), 1449–1483.
2003: Yoav Freund and Robert Schapire, “A Decision Theoretic Generalization of On-Line Learning and an Application to Boosting”, Journal of Computer and System Sciences 55 (1997), 119–139.
2002: Géraud Sénizergues, “L(A)=L(B) ? Decidaility results from complete formal systems”, Theoretical Computer Science 251 (2001), 1–166.
2001: Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy, “Interactive proofs and the hardness of approximating cliques”, Journal of the ACM 43 (1996), 268–292.
Sanjeev Arora and Shmuel Safra, “Probabilistic checking of proofs : a new characterization of NP”, Journal of the ACM 45 (1998), 70–122.
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy,
“Proof verification and the hardness of approximation problems”, Journal of the ACM 45 (1998), 501–555.
2000: Moshe Y. Vardi and Pierre Wolper, “Reasoning about infinite computations”, Information and Computation 115 (1994), 1–37.
1999: Peter W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM Journal on Computing 26 (1997), 1484–1509.
1998: Seinosuke Toda, “PP is as hard as the polynomial-time hierarchy”, SIAM Journal on Computing 20 (1991), 865–877.
1997: Joseph Halpern and Yoram Moses, “Knowledge and common knowledge in a distributed environment”, Journal of the ACM 37 (1990), 549–587.
1996: Alistair Sinclair and Mark Jerrum, “Approximate counting unform generation and rapidly mixing Markov chains”, Information and Computation 82 (1989), 93–133.
Mark Jerrum and Alistair Sinclair, “Approximating the permanent”, SIAM Journal
on Computing 18 (1989), 1149–1178.
1995: Neil Immerman, “Nondeterministic space is closed under complementation”, SIAM Journal on Computing 17 (1988), 935–938.
Róbert Szelepcsényi, “The method of forced enumeration for nondeterministic automata”, Acta Informatica 26 (1988), 279–284.
1994: Johan Håstad, “Almost optimal lower bounds for small depth circuits”, Advances in Computing Research 5 (1989), 143–170.
1993 László Babai and Shlomo Moran, “Arthur-Merlin games : a randomized proof system and a hierarchy of complexity classes”, Journal of Computer and System Sciences 36 (1988), 254–276.
Shafi Goldwasser, Silvio Micali and Charles Rackoff, “The knowledge complexity
of interactive proof systems”, SIAM Journal on Computing 18 (1989), 186–208.
Posts
