ACM Special Interest Group on Algorithms and Computation Theory

Gödel Prize

The Call for Nominations for the 2019 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 25th Gödel Prize will be awarded at the 51st Annual ACM Symposium on Theory of Computing, to be held from 23–26 June, 2019 in Phoenix, Arizona, USA.

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 for the award should be submitted by email to the Award Committee Chair: Please make sure that the Subject line of all nominations and related messages begin with “Goedel Prize 2019”. To be considered, nominations for the 2019 Prize must be received by February 15, 2019.

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.


The 2019 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:

  1. The main results were not published (in either preliminary or final form) in a journal or conference proceedings before January 1st, 2006.
  2. The paper was published in a recognized refereed journal no later than December 31, 2018.

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 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 2019 Award Committee consists of Anuj Dawar (Cambridge University), Robert Krauthgamer (Weizmann Institute), Joan Feigenbaum (Yale University), Giuseppe Persiano (Università di Salerno), Omer Reingold (Chair, Stanford University) and Daniel Spielman (Yale University).

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 the call for nominations are left to the discretion of the Award Committee.


  • 2019: Irit Dinur
  • 2018: Oded Regev
  • 2017: Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith
  • 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