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