Our Organization
The Association for
Computing Machinery

Prizes: Gödel Prize

2016 winners: Stephen Brookes and Peter W. O'Hearn

The Call for Nominations for the 2016 Gödel Prize is available here (pdf). (In case of any discrepancy between the information in the pdf file and what follows, the pdf file is the official document.) Based on the recommendations of an ad hoc committee, the new rules have been endorsed by the EATCS President and the SIGACT Chair in November 2004.

Here are the Old rules which governed the first 12 awards, 1993–2004. Comments can be directed to the current EATCS President or the SIGACT chair.

About the Prize

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 Special Interest Group on Algorithms and Computation Theory of the Association for Computing Machinery (ACM SIGACT). This 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 24th Gödel Prize will be awarded at the 43rd International Colloquium on Automata, Languages and Programming (ICALP), 11-15 July 2016 in Rome, Italy.

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 Neumann's death, in what has become the famous "P versus NP" question.

The Prize includes an award of USD 5000.


Nominations may be made by any member of the scientific community. A nomination should contain a brief summary of the technical content of each nominated paper and a brief explanation of its significance. A copy of the research paper or papers should accompany the nomination.The nomination must state the bibliographic data of the first (preliminary) conference publication of the main results or state that no conference 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. It is the duty of the Award Committee to actively solicit nominations from as broad a spectrum of the theoretical computer science community as possible, so as to ensure that potential award-winning papers are not overlooked. To this end, the Award Committee will accept informal proposals for potential nominees, as well as tentative offers to prepare formal nominations, should they be needed to fulfill the requirements that the paper have two separate recommendations. Those intending to submit a nomination are encouraged to contact the Award Committee Chair well in advance.


Any research paper or series of research papers by a single author or by a team of authors is deemed eligible if the paper was published in a recognized refereed journal before nomination but the main results were not published (in either preliminary or final form) in a journal or conference proceedings 14 or more years before the year of the award. This extended period is in recognition of the fact that the value of fundamental work cannot always be immediately assessed. A conference publication starts the clock because it often is the most effective means of bringing the results to the attention of the community.

The research work nominated for the award should be in the area of theoretical computer science. The term "theoretical computer science" is meant in a broad sense, and encompasses, but is not restricted to, those areas covered by ICALP and STOC. The Award Committee shall have the ultimate authority to decide whether a particular paper is eligible for the Prize.

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 2016 Award Committee consists of Moses Charikar (Stanford University), Orna Kupferman (Hebrew University), Kurt Mehlhorn (Max Planck Institute), Joseph Mitchell (State University of New York at Stony Brook), Andrew Pitts (chair, University of Cambridge) and Madhu Sudan (Harvard University).

Past Winners

  • 2016: Stephen Brookes and Peter W. O'Hearn
  • 2015: Daniel A. Spielman and Shang-Hua Teng
  • 2014: Ronald Fagin, Amnon Lotem, and Moni Naor
  • 2013: Antoine Joux, Dan Boneh, and Matthew K. Franklin
  • 2012: Elias Koutsoupias, Christos H. Papadimitriou, Tim Roughgarden, Éva Tardos, Noam Nisan, and Amir Ronen
  • 2011: Johan T. Håstad
  • 2010: Sanjeev Arora and Joseph S. B. Mitchell
  • 2009: Omer Reingold, Salil Vadhan, and Avi Wigderson
  • 2008: Dan Spielman and Shang-Hua Teng
  • 2007: Alexander A. Razborov and Steven Rudich
  • 2006: Manindra Agrawal, Neeraj Kayal, and Nitin Saxena
  • 2005: Noga Alon, Yossi Matias and Mario Szegedy
  • 2004: Maurice Herlihy and Nir Shavit / Michael Saks and Fotios Zaharoglou
  • 2003: Yoav Freund and Robert Schapire
  • 2002: Géraud Sénizergues
  • 2001: Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, and Mario Szegedy
  • 2000: Moshe Vardi and Pierre Wolper
  • 1999: Peter W. Shor
  • 1998: Seinosuke Toda
  • 1997: Joseph Halpern and Yoram Moses
  • 1996: Mark Jerrum and Alistair Sinclair
  • 1995: Neil Immerman and Róbert Szelepcsényi
  • 1994: Johan Håstad
  • 1993: László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran, and Charles Rackoff
Designed and maintained by Amit Chakrabarti
Latest update: Tue Jun 14 15:53:50 EDT 2016