The Gödel Prize 2025 - Call for Nominations

Deadline: April 11, 2025.

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 33rd Gödel Prize will be awarded at the 57th Annual ACM Symposium on Theory of Computing (STOC 2025) in Prague, Czech Republic, June 23 - 27, 2025.

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 2025 Award Committee consists of Mikołaj Bojańczyk (University of Warsaw), Artur Czumaj (University of Warwick), Yuval Ishai (Technion), Anna Karlin (University of Washington), Marta Kwiatkowska (University of Oxford), Tim Roughgarden (chair, Columbia University).

Eligibility: The 2025 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 main results were not published (in either preliminary or final form) in a journal or conference proceedings before January 1st, 2012.

- The paper was published in a recognized refereed journal no later than December 31, 2024.

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.

Nominations: Nominations for the award should be submitted by email to the Award Committee Chair: 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 2025.” To be considered, nominations for the 2025 Prize must be received by April 11, 2025.

A nomination package should include:

1. A printable copy (or copies) of the journal paper(s) being nominated, together with a complete citation (or citations) thereof.

2. A statement of the date(s) and venue(s) of the first conference or workshop publication(s) of the nominated work(s) or a statement that no such publication has occurred.

3. A brief summary of the technical content of the paper(s) and a brief explanation of its significance.

4. A support letter or letters signed by at least two members of the scientific community.

Additional support letters may also be received and are generally useful. The nominated paper(s) may be in any language. However, if a nominated publication is not in English, the nomination package must include an extended summary written in English.

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 Award Committee. Recent Winners (all winners since 1993 are listed at http://www.sigact.org/Prizes/Godel/ and http://eatcs.org/index.php/goedel-prize):

2024: Ryan Williams

2023: Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf: Exponential Lower Bounds for Polytopes in Combinatorial Optimization. STOC 2012. JACM, 62(2), 17:1-17:23, 2015. Thomas Rothvoss. The matching polytope has exponential extension complexity. STOC 2014. JACM, 64(6),1-19, 2017

2022: Brakerski, Zvika; Vaikuntanathan, Vinod: Efficient Fully Homomorphic Encryption from (Standard) LWE. SIAM Journal on Computing. 43 (2): 831– 871 (preliminary version in Foundations of Computer Science, FOCS 2011). Brakerski, Zvika; Gentry, Craig; Vaikuntanathan, Vinod (2012). “(Leveled) Fully Homomorphic Encryption without Bootstrapping”. ACM Trans. Comput. Theory 6(3): 13:1-13:36 (preliminary version in Innovations in Theoretical Computer Science, ITCS 2012).

2021: Andrei Bulatov: The Complexity of the Counting Constraint Satisfaction Problem. J. ACM 60(5): 34:1–34:41 (2013). Martin E. Dyer and David Richerby: An Effective Dichotomy for the Counting Constraint Satisfaction Problem. SIAM J. Computing. 42(3): 1245–1274 (2013). Jin-Yi Cai and Xi Chen: Complexity of Counting CSP with Complex Weights. J. ACM 64(3): 19:1–19:39 (2017).

2020: Robin A. Moser and Gábor Tardos, A constructive proof of the general Lovász Local Lemma, Journal of the ACM (JACM), Volume Issue 2, 2010 (preliminary version in Symposium on Theory of Computing, STOC 2009)

2019: Irit Dinur, The PCP theorem by gap amplification, Journal of the ACM (JACM), Volume 54 Issue 3, 2007 (preliminary version in Symposium on Theory of Computing, STOC 2006)

2018: Oded Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM (JACM), Volume 56 Issue 6, 2009 (preliminary version in Symposium on Theory of Computing, STOC 2005).

2017: Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith, Calibrating Noise to Sensitivity in Private Data Analysis, Journal of Privacy and Confidentiality, Volume 7, Issue 3, 2016 (preliminary version in Theory of Cryptography, TCC 2006).

2016: Stephen Brookes, A Semantics for Concurrent Separation Logic. Theoretical Computer Science 375(1-3): 227-270 (2007). Peter W. O’Hearn, Resources, Concurrency, and Local Reasoning. Theoretical Computer Science 375(1-3): 271-307 (2007).

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.