| Year | Recipient (University) | Paper |
|---|
| 2024 |
Brice Huang (MIT) |
"Capacity Threshold for the Ising Perceptron" |
| 2023 | Rahul Ilango (MIT) | "SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle" |
| 2022 | Robert Andrews (UIUC) | "On Matrix Multiplication and Polynomial Identity Testing"[3] |
| 2021 | Xiao Mao (MIT) | "Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance" |
| 2020 | Rahul Ilango (MIT) | "The Constant Depth Formula and Partial Function Versions of MCSP are Hard" |
| 2019 | Jason Li (CMU) | "Faster Minimum k-cut of a Simple Graph" |
Josh Alman (MIT)
Lijie Chen (MIT) | "Efficient Construction of Rigid Matrices Using an NP Oracle" |
| 2018 | Shuichi Hirahara (The University of Tokyo) | "Non-black-box Worst-case to Average-case Reductions within NP" |
| Urmila Mahadev (UC Berkeley) | "Classical Verification of Quantum Computation" |
| 2017 | Rasmus Kyng (Yale)
Peng Zhang (Georgia Tech) | "Hardness Results for Structured Linear Systems"[4] |
| 2016 | Michael B. Cohen (MIT) | "Ramanujan Graphs in Polynomial Time"[5] |
| Aviad Rubinstein (Berkeley) | "Settling the Complexity of Computing Approximate Two-Player Nash Equilibria"[6] |
| 2015 | Mika Göös (University of Toronto) | "Lower Bounds for Clique vs. Independent Set" |
Aaron Sidford (MIT)
Yin Tat Lee (MIT)
Sam Chiu-wai Wong (University of California, Berkeley) | "A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization" |
| 2014 | Aaron Sidford (MIT)
Yin Tat Lee (MIT) | "Path-Finding Methods for Linear Programming : Solving Linear Programs in Õ(√rank) Iterations and Faster Algorithms for Maximum Flow" |
| 2013 | Jonah Sherman (University of California, Berkeley) | "Nearly Maximum Flows in Nearly Linear Time" [7] |
| 2012 | Nir Bitansky (Tel Aviv University),
Omer Paneth (Boston University) | "From the Impossibility of Obfuscation to a New Non-Black-Box Simulation Technique" |
| 2011 | Kasper Green Larsen (Aarhus) | "On Range Searching in the Group Model and Combinatorial Discrepancy" |
| Timon Hertli (ETH Zurich) | "3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General" |
| 2010 | Aaron Potechin (MIT) | "Bounds on Monotone Switching Networks for Directed Connectivity" |
| 2009 | Alexander Sherstov (UT Austin) | "The intersection of two halfspaces has high threshold degree" |
| Jonah Sherman (University of California, Berkeley) | "Breaking the Multicommodity Flow Barrier for sqrt(log(n))-Approximations to Sparsest Cut" |
| 2008 | Mihai Pătraşcu (MIT) | "Succincter" |
| 2007 | Per Austrin (KTH) |
"Towards sharp inapproximability for any 2-CSP" |
| 2006 | Nicholas J. A. Harvey (MIT) |
"Algebraic Structures and Algorithms for Matching and Matroid Problems" |
| 2005 | Mark Braverman (Toronto) |
"On the Complexity of Real Functions" |
Tim Abbott (MIT),
Daniel Kane (MIT),
Paul Valiant (MIT) |
"On the Complexity of Two-Player Win-Lose Games" |
| 2004 | Lap Chi Lau (Toronto) | "An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem" |
Marcin Mucha (Warsaw),
Piotr Sankowski (Warsaw) |
"Maximum Matchings via Gaussian Elimination" |
| 2003 | Subhash Khot (Princeton) |
"Hardness of Approximating the Shortest Vector Problem in High Lp Norms" |
| 2002 | Boaz Barak (Weizmann) |
"Constant-Round Coin-Tossing With a Man in the Middle or Realizing Shared Random String Model" |
| Harald Räcke (Paderborn) |
"Minimizing Congestion in General Networks" |
| 2001 | Boaz Barak (Weizmann) | "How To Go Beyond the Black-Box Simulation Barrier" |
| Vladlen Koltun (Tel Aviv) |
"Almost Tight Upper Bounds for Vertical Decompositions in Four Dimensions" |
| 2000 | Piotr Indyk (Stanford) |
"Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation" |
| 1999 | Markus Bläser (Bonn) |
"A 5/2 n2-Lower Bound for the Rank of n×n Matrix Multiplication over Arbitrary Fields" |
| Eric Vigoda (Berkeley) |
"Improved Bounds for Sampling Colorings" |
| 1998 | Kamal Jain (Georgia Tech) |
"Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem" |
| Daniele Micciancio (MIT) |
"The shortest vector problem is NP-hard to approximate to within some constant" |
| 1997 | Santosh Vempala (CMU) |
"A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces" |
| 1996 | Jon Kleinberg (MIT) | "Single-Source Unsplittable Flow" |
| 1995 | Andras Benczur (MIT) |
"A Representation of Cuts within 6/5 Times the Edge Connectivity with Applications" |
| Satyanarayana V. Lokam (Chicago) |
"Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity" |
| 1994 | Rakesh K. Sinha,
T.S. Jayram (Washington) |
"Efficient Oblivious Branching Programs for Threshold Functions" |
| Jeffrey C. Jackson (CMU) |
"An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution" |
| 1993 | Pascal Koiran | "A Weak Version of the Blum, Shub & Smale model" |
| 1992 | Bernd Gärtner (FU Berlin) |
"A Subexponential Algorithm for Abstract Optimization Problems" |
| 1991 | Anna Gal (Chicago) |
"Lower bounds for the complexity of reliable Boolean circuits with noisy gates" |
| Jaikumar Radhakrishnan (Rutgers) | "Better Bounds for Threshold Formulas" |
| 1990 | David Zuckerman (Berkeley) | "General weak random sources" |
| 1989 | Bonnie Berger (MIT)
John Rompel (MIT) | "Simulating (logc n)-wise independence in NC" |
| 1988 | Shmuel Safra (Weizmann) | "On the Complexity of omega-Automata" |
| 1987 | John Canny (MIT) | "A New Algebraic Method for Robot Motion Planning and Real Geometry" |
| Abhiram G. Ranade (Yale) | "How to Emulate Shared Memory (Preliminary Version)" |
| 1986 | Prabhakar Raghavan (Berkeley) |
"Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs" |
| 1985 | Ravi B. Boppana (MIT) | "Amplification of Probabilistic Boolean Formulas" |
| 1984 | Joel Friedman (Harvard) |
"Constructing O(n log n) Size Monotone Formulae for the k-th Elementary Symmetric Polynomial of n Boolean Variables" |
| 1983 | Harry Mairson (Stanford) | "The Program Complexity of Searching a Table" |
| 1982 | Carl Sturtivant (University of Minnesota) | "Generalized Symmetries of Polynomials in Algebraic Complexity" |
| 1981 | F. Thomson Leighton (MIT) | "New Lower Bound Techniques for VLSI" |
