| 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"
|
