Gödel Prize

The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory (ACM SIGACT). The award is named in honor of Kurt Gödel, a famous mathematician whose ideas have greatly influenced this field.

Gödel's connection to theoretical computer science includes him being the first to mention the "P versus NP" question. In a 1956 letter to John von Neumann, Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time, which remains one of the biggest unsolved problems in computer science today.

Kurt Gödel

The Gödel Prize has been awarded since 1993. It is given alternately at ICALP, a major European conference, in even years, and at STOC, a major North American conference, in odd years. To be eligible, a paper must have been published in a refereed journal within the last 14 years. The prize includes a reward of US$5000. The winner is chosen by a committee of six members appointed by the EATCS President and the SIGACT Chair.

Unlike the Gödel Prize, which honors specific papers, the Knuth Prize is awarded to individuals for their overall impact on the field of theoretical computer science.

Recipients

The Gödel Prize is awarded each year for excellent work in theoretical computer science. It is given by two groups: the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory (ACM SIGACT). The prize is named after Kurt Gödel, a famous mathematician who asked an important question in computer science called "P versus NP" in a letter in 1956.

Year	Name(s)	Publication year
1993	László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran, and Charles Rackoff	1988, 1989
1994	Johan Håstad	1989
1995	Neil Immerman and Róbert Szelepcsényi	1988, 1988
1996	Mark Jerrum and Alistair Sinclair	1989, 1989
1997	Joseph Halpern and Yoram Moses	1990
1998	Seinosuke Toda	1991
1999	Peter Shor	1997
2000	Moshe Y. Vardi and Pierre Wolper	1994
2001	Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, and Mario Szegedy	1996, 1998, 1998
2002	Géraud Sénizergues	2001
2003	Yoav Freund and Robert Schapire	1997
2004	Maurice Herlihy, Michael Saks, Nir Shavit and Fotios Zaharoglou	1999, 2000
2005	Noga Alon, Yossi Matias and Mario Szegedy	1999
2006	Manindra Agrawal, Neeraj Kayal, Nitin Saxena	2004
2007	Alexander Razborov, Steven Rudich	1997
2008	Daniel Spielman, Shang-Hua Teng	2004
2009	Omer Reingold, Salil Vadhan, Avi Wigderson	2002, 2008
2010	Sanjeev Arora, Joseph S. B. Mitchell	1998, 1999
2011	Johan Håstad	2001
2012	Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden and Éva Tardos	2009, 2002, 2001
2013	Dan Boneh, Matthew K. Franklin, and Antoine Joux	2003, 2004
2014	Ronald Fagin, Amnon Lotem, and Moni Naor	2003,
2015	Daniel Spielman, Shang-Hua Teng	2011 2013 2014
2016	Stephen Brookes and Peter W. O'Hearn	2007, 2007
2017	Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith	2006
2018	Oded Regev	2009
2019	Irit Dinur	2007
2020	Robin Moser and Gábor Tardos	2010
2021	Andrei Bulatov, Jin-Yi Cai, Xi Chen, Martin Dyer, and David Richerby	2013 2013 2017
2022	Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan	2014, 2014
2023	Samuel Fiorini, Serge Massar, and Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf, and Thomas Rothvoss	2015, 2017
2024	Ryan Williams	2011
2025	Eshan Chattopadhyay and David Zuckerman	2016

Winning papers

The Gödel Prize is an important award given each year for excellent work in theoretical computer science. It is given by two groups: the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory (ACM SIGACT). The prize is named after Kurt Gödel, a famous mathematician who first talked about the "P versus NP" problem in a letter in 1956. This problem is one of the big questions in computer science today.

Recipients

Winning papers

Related articles