年份 | 姓名 | 理论成果 |
1993年 | László Babai Shafi Goldwasser Silvio Micali Shlomo Moran Charles Rackoff | for the development ofinteractive proof systems |
1994年 | Johan Håstad | for an exponential lower bound on the size of constant-depth Boolean circuits (for the parity function). |
1995年 | Neil Immerman Róbert Szelepcsényi | for the Immerman–Szelepcsényi theorem regarding nondeterministic space complexity |
1996年 | Mark Jerrum Alistair Sinclair | for work on Markov chains and the approximation of the permanent of a matrix |
1997年 | Maurice Herlihy Mike Saks Nir Shavit Fotios Zaharoglou | for defining a formal notion of "knowledge" in distributed environments |
1998年 | Seinosuke Toda | for Toda's theorem which showed a connection between counting solutions (PP) and alternation of quantifiers (PH) |
1999年 | Peter Shor | for Shor's algorithm for factoring numbers in polynomial time on a quantum computer |
2000年 | Moshe Y. Vardi Pierre Wolper | for work on temporal logic with finite automata |
2001年 | Sanjeev Arora Uriel Feige Shafi Goldwasser Carsten Lund László Lovász Rajeev Motwani Shmuel Safra Madhu Sudan Mario Szegedy | for the PCP theorem and its applications to hardness of approximation |
2002年 | Géraud Sénizergues | for proving that equivalence of deterministic pushdown automata is decidable |
2003年 | Yoav Freund Robert Schapire | for the AdaBoost algorithm in machine learning |
2004年 | Maurice Herlihy Mike Saks Nir Shavit Fotios Zaharoglou | for applications of topology to the theory of distributed computing |
2005年 | Noga Alon Yossi Matias Mario Szegedy | for their foundational contribution to streaming algorithms |
2006年 | Manindra Agrawal Neeraj Kayal Nitin Saxena | for the AKS primality test |
2007年 | Alexander Razborov Steven Rudich | for natural proofs |
2008年 | Daniel Spielman | for smoothed analysis of algorithms |
2009年 | Omer Reingold Salil Vadhan Avi Wigderson | for zig-zag product of graphs and undirected connectivity in log space |
2010年 | Sanjeev Arora Joseph S. B. Mitchell | for their concurrent discovery of a polynomial-time approximation scheme (PTAS) for the Euclidean Travelling Salesman Problem (ETSP) |
2011年 | Johan Håstad | for proving optimal inapproximability result for various combinatorial problems |
2012年 | Elias Koutsoupias Christos Papadimitriou Noam Nisan Amir Ronen Tim Roughgarden Éva Tardos | for laying the foundations of algorithmic game theory |
2013年 | Dan Boneh Matthew K. Franklin Antoine Joux | for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography |
2014年 | Ronald Fagin Amnon Lotem Moni Naor | for Optimal Aggregation Algorithms for Middlewar |
2015年 | 滕尚华 Daniel Spielman | for their series of papers on nearly-linear-time Laplacian solvers |