The Gödel Prize 2017 - Call for Nominations
Deadline: February 15, 2017
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 25th Gödel Prize will be awarded at the 49th Annual
ACM Symposium on Theory of Computing, to be held from 19-23 June,
2017 in Montreal, Canada.
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 5,000.
Award Committee: The 2017 Award Committee consists of
Moses Charikar (Stanford University), Orna Kupferman (Hebrew
University), Kurt Mehlhorn (Max Planck Institute), Giuseppe
Persiano (Universitŕ di Salerno), Omer Reingold (Stanford
University) and Madhu Sudan (Chair, Harvard University).
Eligibility: The 2017 Prize rules are given below and they
supersede any different interpretation of the generic rule to be
found on websites of both SIGACT and EATCS. Any research paper or
series of papers by a single author or by a team of authors is
deemed eligible if:
The research work nominated for the award should be in the area
of theoretical computer science. 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
- The main results were not published (in either
preliminary or final form) in a journal or conference
proceedings before January 1st, 2004.
- The paper was published in a recognized refereed journal
no later than December 31, 2016.
Nominations: Nominations for the award should be
submitted by email to the Award Committee Chair:
firstname.lastname@example.org. Please make sure that the Subject line of
all nominations and related messages begin with "Goedel Prize
2017." To be considered, nominations for the 2017 Prize must be
received by February 15, 2017.
Any member of the scientific community can make nominations. The
Award Committee may 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.
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
distinct nominations, or one nomination including recommendations
from at least two different people. Additional
recommendations may also be enclosed and are generally useful. The
Award Committee encourages recommendation and support letters to
be mailed separately, without being necessarily shared with the
nominator(s). The rest of the nomination package should be sent in
a single email whenever possible. Those intending to submit a
nomination should contact the Award Committee Chair by email well
in advance. The Chair will answer questions about eligibility,
encourage coordination among different nominators for the same
paper(s), and also accept informal proposals of potential nominees
or tentative offers to prepare formal nominations. The committee
maintains a database of past nominations for eligible papers, but
fresh nominations for the same papers (especially if they
highlight new evidence of impact) are always welcome.
Selection Process: The Award Committee is free to use any
other sources of information in addition to the ones mentioned
above. It may split the award among multiple papers, or declare no
winner at all. All matters relating to the selection process left
unspecified in this document are left to the discretion of the
Recent Winners (all winners since 1993 are listed at http://www.sigact.org/Prizes/Godel/
2016: S. Brookes, A Semantics for Concurrent Separation
Logic. Theoretical Computer Science 375(1-3): 227-270
(2007). P. W. O'Hearn, Resources, Concurrency, and Local
Reasoning. Theoretical Computer Science 375(1-3): 271-307
2015: Dan Spielman and Shang-Hua Teng, Nearly-linear
time algorithms for graph partitioning, graph sparsification,
and solving linear systems, Proc. 36th ACM Symposium on
Theory of Computing, pp. 81-90, 2004; Spectral sparsification
of graphs, SIAM J. Computing 40:981-1025, 2011; A local
clustering algorithm for massive graphs and its application to
nearly linear time graph partitioning, SIAM J. Computing
42:1-26, 2013; Nearly linear time algorithms for
preconditioning and solving symmetric, diagonally dominant
linear systems, SIAM J. Matrix Anal. Appl. 35:835-885, 2014.
2014: Ronald Fagin, Amnon Lotem, and Moni Naor, Optimal
Aggregation Algorithms for Middleware, Journal of Computer
and System Sciences 66(4): 614-656, 2003.
2013: Antoine Joux, A one round protocol for tripartite
Diffie-Hellman, J. Cryptology 17(4): 263-276, 2004. Dan
Boneh and Matthew K. Franklin, Identity-Based Encryption from
the Weil pairing, SIAM J. Comput. 32(3): 586-615,
2012: Elias Koutsoupias and Christos Papadimitriou, Worst-case
equilibria, Computer Science Review 3(2): 65-69, 2009. Tim
Roughgarden and Éva Tardos, How bad is selfish routing?,
Journal of the ACM 49(2): 236- 259, 2002. Noam Nisan and Amir
Ronen, Algorithmic mechanism design, Games and
Economic Behavior 35(1-2): 166-196, 2001.