Year |
Name(s) |
Notes |
Publication year |
1993 | László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran, and Charles Rackoff | for the development of interactive proof systems | 1988,[paper 1] 1989[paper 2] |
1994 | Johan Håstad | for an exponential lower bound on the size of constant-depth Boolean circuits (for the parity function). | 1989[paper 3] |
1995 | Neil Immerman and Róbert Szelepcsényi | for the Immerman–Szelepcsényi theorem regarding nondeterministic space complexity | 1988,[paper 4] 1988[paper 5] |
1996 | Mark Jerrum and Alistair Sinclair | for work on Markov chains and the approximation of the permanent of a matrix | 1989,[paper 6] 1989[paper 7] |
1997 | Joseph Halpern and Yoram Moses | for defining a formal notion of "knowledge" in distributed environments | 1990[paper 8] |
1998 | Seinosuke Toda | for Toda's theorem, which showed a connection between counting solutions (PP) and alternation of quantifiers (PH) | 1991[paper 9] |
1999 | Peter Shor | for Shor's algorithm for factoring numbers in polynomial time on a quantum computer | 1997[paper 10] |
2000 | Moshe Y. Vardi and Pierre Wolper | for work on temporal logic with finite automata | 1994[paper 11] |
2001 | Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, and Mario Szegedy | for the PCP theorem and its applications to hardness of approximation | 1996,[paper 12] 1998,[paper 13] 1998[paper 14] |
2002 | Géraud Sénizergues | for proving that equivalence of deterministic pushdown automata is decidable | 2001[paper 15] |
2003 | Yoav Freund and Robert Schapire | for the AdaBoost algorithm in machine learning | 1997[paper 16] |
2004 | Maurice Herlihy, Michael Saks, Nir Shavit and Fotios Zaharoglou | for applications of topology to the theory of distributed computing | 1999,[paper 17] 2000[paper 18] |
2005 | Noga Alon, Yossi Matias and Mario Szegedy | for their foundational contribution to streaming algorithms | 1999[paper 19] |
2006 | Manindra Agrawal, Neeraj Kayal, Nitin Saxena | for the AKS primality test | 2004[paper 20] |
2007 | Alexander Razborov, Steven Rudich | for natural proofs | 1997[paper 21] |
2008 | Daniel Spielman, Shang-Hua Teng | for smoothed analysis of algorithms | 2004[paper 22] |
2009 | Omer Reingold, Salil Vadhan, Avi Wigderson | for zig-zag product of graphs and undirected connectivity in log space | 2002,[paper 23] 2008[paper 24] |
2010 | Sanjeev Arora, Joseph S. B. Mitchell | for their concurrent discovery of a polynomial-time approximation scheme for the Euclidean Travelling Salesman Problem | 1998,[paper 25] 1999[paper 26] |
2011 | Johan Håstad | for proving optimal inapproximability results for various combinatorial problems | 2001[paper 27] |
2012 | Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden and Éva Tardos | for laying the foundations of algorithmic game theory[3] | 2009,[paper 28] 2002,[paper 29] 2001[paper 30] |
2013 | Dan Boneh, Matthew K. Franklin, and Antoine Joux | for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography[4] | 2003,[paper 31]
2004[paper 32] |
2014 | Ronald Fagin, Amnon Lotem [fr], and Moni Naor | for Optimal Aggregation Algorithms for middleware[5] | 2003,[paper 33] |
2015 | Daniel Spielman, Shang-Hua Teng |
for their series of papers on nearly-linear-time Laplacian solvers[6] |
2011[paper 34]
2013[paper 35]
2014[paper 36] |
2016 |
Stephen Brookes and Peter W. O'Hearn |
for their invention of Concurrent Separation Logic |
2007,[paper 37] 2007[paper 38] |
2017[2] |
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith |
for the invention of differential privacy |
2006[paper 39] |
2018[7] |
Oded Regev |
for introducing the learning with errors problem |
2009[paper 40] |
2019[8] |
Irit Dinur |
for her new proof of the PCP theorem by gap amplification |
2007[paper 41] |
2020[9] |
Robin Moser and Gábor Tardos |
for their constructive proof of the Lovász local lemma |
2010[paper 42] |
2021[10] |
Andrei Bulatov, Jin-Yi Cai, Xi Chen, Martin Dyer, and David Richerby |
for their work on the classification of the counting complexity of constraint satisfaction problems |
2013[paper 43] 2013[paper 44] 2017[paper 45] |
2022[11] |
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan |
for their transformative contributions to cryptography by constructing efficient fully homomorphic encryption (FHE) schemes |
2014,[paper 46] 2014[paper 47] |
2023[12] |
Samuel Fiorini, Serge Massar, and Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf, and Thomas Rothvoss |
for showing that any extended formulation for the TSP polytope has exponential size |
2015,[paper 48] 2017[paper 49] |
2024[13] |
Ryan Williams |
for his work on circuit lower bounds and the “algorithms to lower bounds” paradigm |
2011[paper 50] |