The Gödel Prize is a prize for outstanding papers in theoretical computer science

Theoretical computer science

Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....

, named after Kurt Gödel

Kurt Gödel

Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...

 and awarded jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery

Association for Computing Machinery

The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...

 Special Interest Group on Algorithms and Computation Theory (ACM SIGACT

ACM SIGACT

ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer.-Publications:...

).

The Gödel Prize has been awarded annually since 1993. It includes an award of $5000. The prize is awarded either at STOC (ACM Symposium on Theory of Computing

Symposium on Theory of Computing

STOC, the Annual ACM Symposium on Theory of Computing is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for Computer Machinery special interest group SIGACT.As...

, one of the main North America

North America

North America is a continent wholly within the Northern Hemisphere and almost wholly within the Western Hemisphere. It is also considered a northern subcontinent of the Americas...

n conferences in theoretical computer science) or ICALP (International Colloquium on Automata, Languages and Programming

International Colloquium on Automata, Languages and Programming

ICALP, the International Colloquium on Automata, Languages and Programming is an academic conference organized annually by the European Association for Theoretical Computer Science and held in different locations around Europe...

, one of the main Europe

Europe

Europe is, by convention, one of the world's seven continents. Comprising the westernmost peninsula of Eurasia, Europe is generally 'divided' from Asia to its east by the watershed divides of the Ural and Caucasus Mountains, the Ural River, the Caspian and Black Seas, and the waterways connecting...

an conferences in the field). To be eligible for the prize, a paper must be published in a refereed journal within the last 14 (formerly 7) years.

Recipients

Year	Name(s)	Notes	Publication year
1993	László Babai László Babai László Babai is a Hungarian professor of mathematics and computer science at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields... , Shafi Goldwasser Shafi Goldwasser Shafrira Goldwasser is the RSA Professor of electrical engineering and computer science at MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel.-Biography:... , Silvio Micali Silvio Micali Silvio Micali is an Italian-born computer scientist at MIT Computer Science and Artificial Intelligence Laboratory and a professor of computer science in MIT's Department of Electrical Engineering and Computer Science since 1983. His research centers on the theory of cryptography and information... , Shlomo Moran Shlomo Moran Shlomo Moran is an Israeli computer scientist, the Bernard Elkin Chair in Computer Science at the Technion – Israel Institute of Technology in Haifa, Israel.Moran received his Ph.D... , and Charles Rackoff Charles Rackoff Charles Weill Rackoff is an American cryptologist. Born and raised in New York City, Rackoff attended MIT as both an undergraduate and graduate student, and earned a Ph.D. degree in Computer Science in 1974. He spent a year as a postdoctoral scholar at INRIA in France.He currently works at the...	for the development of interactive proof system Interactive proof system In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a... s	1988, 1989
1994	Johan Håstad Johan Håstad Johan Torkel Håstad is a Swedish theoretical computer scientist most known for his work on computational complexity theory. He was the recipient of the Gödel Prize in 1994 and 2011 and the ACM Doctoral Dissertation Award in 1986, among other prizes...	for an exponential lower bound on the size of Circuit complexity In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them....  constant-depth Boolean circuits (for the parity function Parity function In Boolean algebra, a parity function is a Boolean function whose value is 1 if the input vector has an odd number of ones.The parity function is notable for its role in theoretical investigation of circuit complexity of Boolean functions.-Definition:... ).	1989
1995	Neil Immerman Neil Immerman Neil Immerman is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst...  and Róbert Szelepcsényi Róbert Szelepcsényi Róbert Szelepcsényi was a Slovak student of Hungarian descent and a member of the Faculty of Mathematics, Physics and Informatics of Comenius University in Bratislava....	for the Immerman-Szelepcsényi theorem Immerman-Szelepcsényi theorem In computational complexity theory, the Immerman–Szelepcsényi theorem was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for which they shared the 1995 Gödel Prize. In its general form the theorem states that NSPACE = co-NSPACE for any function s ≥ log n...  regarding nondeterministic space complexity	1988, 1988
1996	Mark Jerrum Mark Jerrum Mark Richard Jerrum is a British computer scientist and computational theorist.Jerrum received his Ph.D. in computer science in 1981 from University of Edinburgh under the supervision of Leslie Valiant...  and Alistair Sinclair Alistair Sinclair Alistair Sinclair is a British computer scientist and computational theorist.Sinclair received his B.A. in Mathematics from St. John’s College, Cambridge in 1979, and his Ph.D. in Computer Science from the University of Edinburgh in 1988 under the supervision of Mark Jerrum...	for work on Markov chains and the approximation of the permanent	1989, 1989
1997	Joseph Halpern Joseph Halpern Joseph Yehuda Halpern is a professor of computer science at Cornell University. Most of his research is on reasoning about knowledge and uncertainty....  and Yoram Moses Yoram Moses Yoram Moses is a Professor in the Electrical Engineering Department at the Technion - Israel Institute of Technology.Yoram Moses received a B.Sc. in mathematics from the Hebrew University of Jerusalem in 1981, and a Ph.D. in Computer Science from Stanford University in 1986...	for defining a formal notion of "knowledge" in distributed environments	1990
1998	Seinosuke Toda Seinosuke Toda is a computer scientist working at the Nihon University in Tokyo. He was a recipient of the 1998 Gödel Prize for proving Toda's theorem.-External links:* at the Nihon University....	for Toda's theorem Toda's theorem Toda's theorem was proven by Seinosuke Toda in his paper "PP is as Hard as the Polynomial-Time Hierarchy" and was given the 1998 Gödel Prize. The theorem states that the entire polynomial hierarchy PH is contained in PPP; this implies a closely related statement, that PH is contained in P#P...  which showed a connection between counting solutions (PP PP (complexity) In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time... ) and alternation of quantifiers (PH)	1991
1999	Peter Shor Peter Shor Peter Williston Shor is an American professor of applied mathematics at MIT, most famous for his work on quantum computation, in particular for devising Shor's algorithm, a quantum algorithm for factoring exponentially faster than the best currently-known algorithm running on a classical...	for Shor's algorithm Shor's algorithm Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm for integer factorization formulated in 1994...  for factoring Integer factorization In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....  numbers in polynomial time on a quantum computer Quantum computer A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...	1997
2000	Moshe Y. Vardi Moshe Y. Vardi Moshe Ya'akov Vardi is a Professor of Computer Science at Rice University, USA. He is the Karen Ostrum George Professor in Computational Engineering, Distinguished Service Professor, and Director of the Computer and Information Technology Institute...  and Pierre Wolper	for work on temporal logic Temporal logic In logic, the term temporal logic is used to describe any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time. In a temporal logic we can then express statements like "I am always hungry", "I will eventually be hungry", or "I will be hungry...  with finite automata	1994
2001	Sanjeev Arora Sanjeev Arora Sanjeev Arora is a theoretical computer scientist who is best known for his work on probabilistically checkable proofs and, in particular, the PCP theorem. He is currently the Charles C... , Uriel Feige Uriel Feige Uriel Feige is an Israeli computer scientist who was a doctoral student of Adi Shamir. He is notable for co-inventing the Feige–Fiat–Shamir identification scheme along with Amos Fiat and Adi Shamir... , Shafi Goldwasser Shafi Goldwasser Shafrira Goldwasser is the RSA Professor of electrical engineering and computer science at MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel.-Biography:... , Carsten Lund Carsten Lund Carsten Lund is a Danish-born theoretical computer scientist, currently working at AT&T Labs in Florham Park, New Jersey, United States.Lund was born in Aarhus, Denmark, and received the... , László Lovász László Lovász László Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010.... , Rajeev Motwani Rajeev Motwani Rajeev Motwani was a professor of Computer Science at Stanford University whose research focused on theoretical computer science. He was an early advisor and supporter of companies including Google and PayPal, and a special advisor to Sequoia Capital. He was a winner of the Gödel Prize in... , Shmuel Safra Shmuel Safra Shmuel Safra is a Professor of Computer Science at Tel Aviv University, Israel. Born in Jerusalem.Safra's research areas include Complexity Theory and Automata Theory... , Madhu Sudan Madhu Sudan Madhu Sudan is an Indian computer scientist, professor of computer science at the Massachusetts Institute of Technology and a member of MIT Computer Science and Artificial Intelligence Laboratory.-Career:... , and Mario Szegedy Mario Szegedy Mario Szegedy is a Hungarian computer scientist, professor of computer science at Rutgers University. He received his Ph.D. in computer science in 1989 from the University of Chicago...	for the PCP theorem PCP theorem In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity .The PCP theorem says that for some universal constant K, for every...  and its applications to hardness of approximation	1996, 1998, 1998
2002	Géraud Sénizergues Géraud Sénizergues Géraud Sénizergues is a French computer scientist at the University of Bordeaux. He won the 2002 Gödel Prize "for proving that equivalence of deterministic pushdown automata is decidable"-External links:*...	for proving that equivalence of deterministic pushdown automata Deterministic pushdown automaton In automata theory, a pushdown automaton is a finite automaton with an additional stack of symbols; its transitions can take the top symbol on the stack and depend on its value, and they can add new top symbols to the stack....  is decidable Decidability (logic) In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas can be effectively...	2001
2003	Yoav Freund Yoav Freund Yoav Freund is a researcher and professor at the University of California, San Diego who mainly works on machine learning, probability theory and related fields and applications.From his homepage:...  and Robert Schapire Robert Schapire Robert Elias Schapire is a professor and researcher in the computer science department at Princeton University. His primary specialty is theoretical and applied machine learning....	for the AdaBoost AdaBoost AdaBoost, short for Adaptive Boosting, is a machine learning algorithm, formulated by Yoav Freund and Robert Schapire. It is a meta-algorithm, and can be used in conjunction with many other learning algorithms to improve their performance. AdaBoost is adaptive in the sense that subsequent...  algorithm	1997
2004	Maurice Herlihy Maurice Herlihy Maurice Herlihy is a computer scientist active in the field of multiprocessor synchronization. Herlihy has contributed to the design of concurrent algorithms, and in particular to the exposition and quantification of the properties and uses of hardware synchronization operations... , Michael Saks Michael Saks (mathematician) Michael Ezra Saks is a professor and was director of the Mathematics Graduate Program at Rutgers University. Saks received his Ph.D from the Massachusetts Institute of Technology in 1980 after completing his dissertation entitled Duality Properties of Finite Set Systems under his advisor Daniel J... , Nir Shavit Nir Shavit Nir Shavit is a Professor in the Computer Science Department at Tel Aviv University.Nir Shavit received B.Sc. and M.Sc. degrees in Computer Science from the Technion - Israel Institute of Technology in 1984 and 1986, and a Ph.D. in Computer Science from the Hebrew University of Jerusalem in 1990...  and Fotios Zaharoglou	for applications of topology Topology Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...  to the theory of distributed computing Distributed computing Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...	1999,. Gödel prize lecture 2000
2005	Noga Alon Noga Alon Noga Alon is an Israeli mathematician noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers.- Academic background :... , Yossi Matias and Mario Szegedy Mario Szegedy Mario Szegedy is a Hungarian computer scientist, professor of computer science at Rutgers University. He received his Ph.D. in computer science in 1989 from the University of Chicago...	for their foundational contribution to streaming algorithm Streaming algorithm In computer science, streaming algorithms are algorithms forprocessing data streams in which the input is presented as a sequence ofitems and can be examined in only a few passes... s	1999. First presented at the Symposium on Theory of Computing Symposium on Theory of Computing STOC, the Annual ACM Symposium on Theory of Computing is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for Computer Machinery special interest group SIGACT.As...  (STOC) in 1996.
2006	Manindra Agrawal Manindra Agrawal Manindra Agrawal is a professor at the department of computer science and engineering and the Dean of Resource, Planning and Generation at the Indian Institute of Technology, Kanpur. He is also the recipient of the first Infosys Prize for Mathematics.-Early life:Manindra Agrawal obtained a... , Neeraj Kayal Neeraj Kayal Neeraj Kayal is an Indian computer scientist. Kayal was born and raised in Guwahati, India.Kayal graduated with a B.Tech from the Computer Science Department of the Indian Institute of Technology, Kanpur , India in 2002... , Nitin Saxena Nitin Saxena Nitin Saxena is an Indian scientist, active in the fields of mathematics and theoretical computer science. His research focuses on topics in computational complexity, especially algebraic approaches....	for the AKS primality test AKS primality test The AKS primality test is a deterministic primality-proving algorithm created and published by three Indian Institute of Technology Kanpur computer scientists, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, on August 6, 2002, in a paper titled "PRIMES is in P"...	2004
2007	Alexander Razborov Alexander Razborov Aleksandr Aleksandrovich Razborov , sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist who won the Nevanlinna Prize in 1990 for introducing the "approximation method" in proving Boolean circuit lower bounds of some essential algorithmic problems, and... , Steven Rudich Steven Rudich Steven Rudich is a professor in the Carnegie Mellon School of Computer Science. In 1994, he and Alexander Razborov proved that a large class of combinatorial arguments, dubbed natural proofs were unlikely to answer many of the important problems in computational complexity theory. For this work,...	for natural proof Natural proof In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one. While these proofs are in some sense "natural", it can be shown that no such proof can possibly be used to solve the P vs... s	1997
2008	Daniel Spielman Daniel Spielman Daniel Alan Spielman is professor of Applied Mathematics and Computer Science at Yale University .... , Shanghua Teng Shanghua Teng Shang-Hua Teng is the chairman of the Computer Science Department at the Viterbi School of Engineering of the University of Southern California. In 2008 he was awarded the Gödel Prize for his joint work on smoothed analysis of algorithms with Daniel Spielman...	for smoothed analysis Smoothed analysis Smoothed analysis is a way of measuring the complexity of an algorithm. It gives a more realistic analysis of the practical performance of the algorithm, such as its running time, than using worst-case or average-case scenarios....  of algorithms	2004
2009	Omer Reingold Omer Reingold Omer Reingold is a faculty member of the Foundations of Computer Science Group at the Weizmann Institute of Science, Israel. He received the 2005 Grace Murray Hopper Award for his work in finding a deterministic logarithmic-space algorithm for ST-connectivity in undirected graphs... , Salil Vadhan Salil Vadhan Salil Vadhan is Vicky Joseph Professor of Computer Science and Applied Mathematics at Harvard University. He obtained his PhD in Applied Mathematics from Massachusetts Institute of Technology in 1999, where his advisor was Shafi Goldwasser. His research centers around the interface between... , Avi Wigderson Avi Wigderson Avi Wigderson is an Israeli mathematician and computer scientist, a professor of mathematics at the Institute for Advanced Study in Princeton. His research interests include complexity theory, parallel algorithms, graph theory, cryptography, distributed computing, and neural...	for zig-zag product Zig-zag product In graph theory, the zig-zag product of regular graphs G,H, denoted by G \circ H, takes a large graph and a small graph , and produces a graph that approximately inherits the size of the large one but the degree of the small one...  of graphs Graph (mathematics) In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...  and undirected connectivity in log space	2002, 2008
2010	Sanjeev Arora Sanjeev Arora Sanjeev Arora is a theoretical computer scientist who is best known for his work on probabilistically checkable proofs and, in particular, the PCP theorem. He is currently the Charles C... , Joseph S. B. Mitchell Joseph S. B. Mitchell Joseph S. B. Mitchell is an American computer scientist and mathematician. He is Professor of Applied Mathematics and Statistics and Research Professor of Computer Science at the Stony Brook University.-Biography:...	for their concurrent discovery of a polynomial-time approximation scheme Polynomial-time approximation scheme In computer science, a polynomial-time approximation scheme is a type of approximation algorithm for optimization problems ....  (PTAS) for the Euclidean Travelling Salesman Problem Travelling salesman problem The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...  (ETSP)	1998, 1999
2011	Johan Håstad Johan Håstad Johan Torkel Håstad is a Swedish theoretical computer scientist most known for his work on computational complexity theory. He was the recipient of the Gödel Prize in 1994 and 2011 and the ACM Doctoral Dissertation Award in 1986, among other prizes...	for proving optimal inapproximability result for various combinatorial problems	2001