Gödel Prize (together with ACM SIGACT)

The Gödel Prize for outstanding papers in the area of theoretical computer science is sponsored jointly by the ACM SIGACT. This award is presented annually, with the presentation taking place alternately at the International Colloquium on Automata, Languages, and Programming (ICALP) and ACM Symposium on the Theory of Computing (STOC). 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 $5000 (US).

Nominations and Eligibility

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.

Nominations for the award should be submitted by email to the Award Committee Chair

Madhu Sudan
University of California at Berkeley
This e-mail address is being protected from spambots. You need JavaScript enabled to view it

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.

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.

More information can be found on the ACM SIGACT Gödel Prize site.

2016 / S. Brookes, P. W. O’Hearn

Place: ICALP (Rome)

Committee:  Moses Charikar (Stanford University), Orna Kupferman (Hebrew University). Kurt Mehlhorn (Max Planck Institute), Joe Mitchell (SUNY at Stony Brook), Andrew Pitts (University of Cambridge, chair) and Madhu Sudan (Harvard University).

2015 / Daniel A. Spielman, Shang-Hua Teng

Place: STOC (Portland, OR)

Committee: Krzysztof Apt (CWI Amsterdam), Kurt Mehlhorn (Max Planck Institute), Joseph Mitchell (Stony Brook University), Andrew Pitts (University of Cambridge), Madhu Sudan (Microsoft Research) and Éva Tardos, Chair (Cornell University).

2014 / Ronald Fagin, Amnon Lotem, Moni Naor

Place: ICALP (Copenhagen)

Committee: Krzysztof R. Apt (CWI Amsterdam and University of Amsterdam), Giuseppe Italiano Chair (Università di Roma Tor Vergata), University), Joseph Mitchell (State University of New York at Stony Brook), Andrew Pitts (University of Cambridge), Daniel Spielman (Yale University), and Éva Tardos (Cornell University).

2013 / Antoine Joux, Dan Boneh, Matthew K. Franklin

Place: STOC (Palo Alto)

Committee: Sanjeev Arora (Princeton), Daniel Spielman (Yale University), Eva Tardos (Cornell University), Krzysztof R. Apt (University of Amsterdam), Josep Diaz (Universitat Politecnica de Catalunya ), Giuseppe F. Italiano (Università di Roma Tor Vergata).

2012 / Elias Koutsoupias, Christos H. Papadimitriou, Tim Roughgarden, Eva Tardos, Noam Nisan, Amir Ronen

Place: ICALP (Warwick)

Committee: Sanjeev Arora (Princeton), Josep Diaz (Universitat Politecnica de Catalunya), Giuseppe F. Italiano (Università di Roma Tor Vergata), Mogens Nielsen (Chair, University of Aarhus), Daniel A. Spielman (Yale University), Eli Upfal (Brown University).

2011 / Johan T. Hastad

Place: STOC (San Jose, CA)

Committee: Sanjeev Arora (Princeton), Josep Diaz (Universitat Politecnica de Catalunya), Cynthia Dwork (Microsoft Research), Mogens Nielsen (University of Aarhus), Mike Paterson (University of Warwick), Eli Upfal (Chair, Brown University).

2010 / Sanjeev Arora, Joseph S.B. Mitchell

Place: ICALP (Bordeaux)

Committee: Cynthia Dwork (Microsoft), Johan Håstad (KTH, Stockholm), Jean-Pierre Jouannaud (Chair, LIX, École Polytechnique), Mogen Nielsen (Aarhus University), Mike Paterson (University of Warwick), Eli Upfal (Brown University)

Photos from ICALP 2010 by Manfred Kudlek

2009 / Omer Reingold, Salil Vadhan, Avi Wigderson

Place: STOC (Bethesda, MD)

Committee: Cynthia Dwork (Microsoft), Shafi Goldwasser (Chair, MIT and Weizmann Institute), Johan Håstad (KTH, Stockholm), Jean-Pierre Jouannaud (LIX, École Polytechnique), Mike Paterson (University of Warwick), Colin Stirling (University of Edinburgh)

2008 / Daniel A. Spielman, Shang-Hua Teng

Place: ICALP (Reykjavik)

Committee: Volker Diekert (Chair, Universität Stuttgart), Shafi Goldwasser (MIT and Weizmann Institute), Johan Håstad (KTH Stockholm), Jean-Pierre Jouannaud (École Polytechnique and Université Paris-Sud), Christos Papadimitriou (UC Berkeley), Colin Stirling (University of Edinburgh)

2007 / Alexander A. Razborov, Steven Rudich

Place: STOC (San Diego)

Committee: John Reif (Chair, Duke University), Volker Diekert (Universität Stuttgart), Shafi Goldwasser (MIT and Weizmann Institute), Christos Papadimitriou (UC Berkeley), Colin Stirling (University of Edinburgh), Paul Vitanyi (CWI, Amsterdam)

2006 / Manindra Agrawal, Neeraj Kayal, Nitin Saxena

Place: ICALP (Venice)

Committee: Pierre-Louis Curien (Chair), Volker Diekert, Christos Papadimitriou, John Reif, Jeffrey Ullman, Paul Vitanyi

2005 / Noga Alon, Yossi Matias, Mario Szegedy

Place: STOC (Baltimore)

Committee: G. Ausiello, L. Babai (Chair), P.-L. Curien, J. Reif, J. Ullman, P. Vitanyi

2004 / Maurice Herlihy, Nir Shavit, Michael Saks, Fotios Zaharoglou

Place: ICALP (Turku)

Committee: G. Ausiello, L. Babai, P.-L. Curien, Z. Galil, J. Karhumäki (Chair), J. Ullman

2003 / Yoav Freund, Robert Schapire

Place: STOC (San Diego)

Committee: G. Ausiello, L. Babai, Z. Galil, J. Karhumäki, D. Kozen (Chair), U. Montanari

2002 / Géraud Sénizergues

Place: ICALP (Málaga)

Committee: U. Montanari, D. Kozen, J. Karhumäki, Z. Galil, J. Simon, K. Mehlhorn (Chair)

2001 / Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, Laszlo Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, Mario Szegedy

Place: ICALP (Crete)

Committee: F. Preparata, J. Simon, D. Kozen, K. Mehlhorn, U. Montanari, W. Thomas (Chair)

2000 / Moshe Y. Vardi, Pierre Wolper

Place: STOC (Portland)

Committee: L. Valiant, F. Preparata (Chair), J. Simon, A. Pnueli, W. Thomas, K. Mehlhorn

1999 / Peter W. Shor

Place: STOC (Philadelphia)

Committee: R . Graham (Chair), L. Valiant, F. Preparata, A. Pnueli, E. Welzl, W. Thomas

1998 / Seinosuke Toda

Place: ICALP (Aalborg)

Committee: R. Graham, D. Johnson, L. Valiant, A. Pnueli, E. Welzl (Chair), G. Rozenberg

1997 / Joseph Halpern, Yoram Moses

Place: ICALP (Bologna)

Committee: R. Graham, D. Johnson, J. Hartmanis, G. Plotkin, E. Welzl, G. Rozenberg (Chair)

1996 / Mark Jerrum, Alistair Sinclair

Place: FOCS (Philadelphia)

Committee: M. Rabin (Chair), D. Johnson, J. Hartmanis, G. Plotkin, J. van Leeuwen, G. Rozenberg

1995 / Neil Immerman, Róbert Szelepcsényi

Place: FOCS (Las Vegas)

Committee: M. Rabin, R. Karp (Chair), J. Hartmanis, G. Plotkin, J. van Leeuwen, A. Salomaa

1994 / Johan Håstad

Place: ICALP (Jerusalem)

Committee: M. Rabin, R. Karp, S. Cook, R. Milner, J. van Leeuwen, A. Salomaa (Chair)

1993 / László Babai, Shlomo Moran, Shafi Goldwasser, Silvio Micali, Charles Rackoff

Place: STOC (San Diego)

Committee: A. Chi-Chih Yao (Chair), A. Salomaa, M. Rabin, R. Karp, S. Cook, R. Milner

e-max.it: your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.