| Year | Title | Authors |
|---|---|---|
| 2018 | Classical Verification of Quantum Computation | Urmila Mahadev, University of California Berkeley |
| 2018 | Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time Diptarka | Chakraborty, Computer Science Institute of Charles University Debarati Das, Computer Science Institute of Charles University Elazar Goldenberg, The Academic College Of Tel Aviv-Yaffo Michal Koucký, Computer Science Institute of Charles University Michael Saks, Rutgers University |
| 2018 | Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion | Subhash Khot, New York University Dor Minzer, Tel-Aviv University Muli Safra, Tel-Aviv University |
| 2017 | A dichotomy theorem for nonuniform CSPs | Andrei A. Bulatov, Simon Fraser University |
| 2017 | The Matching Problem in General Graphs is in Quasi-NC | Ola Svensson & Jakub Tarnawski, École polytechnique fédérale de Lausanne |
| 2017 | The Proof of CSP Dichotomy Conjecture | Dmitriy Zhuk, Lomonosov Moscow State University |
| 2016 | Settling the Complexity of Computing Approximate Two-Player Nash Equilibria | Aviad Rubinstein, University of California Berkeley |
| 2016 | Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning | Ran Raz, Weizmann Institute of Science |
| 2015 | An average-case depth hierarchy theorem for Boolean circuits | Benjamin Rossman, National Institute of Informatics Rocco A. Servedio, Columbia University Li-Yang Tan, University of California Berkeley |
| 2014 | Path Finding Methods for Linear Programming: Solving Linear Programs in O(sqrt(rank)) Iterations and Faster Algorithms for Maximum Flow | Yin Tat Lee & Aaron Sidford, Massachusetts Institute of Technology |
| 2013 | Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back | Aleksander Mądry, École Polytechnique Fédérale de Lausanne |
| 2012 | A multi-prover interactive proof for NEXP sound against entangled provers | Tsuyoshi Ito, NEC Labs America Thomas Vidick, Massachusetts Institute of Technology |
| 2012 | A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2 | Julia Chuzhoy, Toyota Technological Institute at Chicago Shi Li, Princeton University |
| 2011 | A Randomized Rounding Approach to the Traveling Salesman Problem | Shayan Oveis Gharan, Stanford University Amin Saberi, Stanford University Mohit Singh, McGill University |
| 2011 | A Polylogarithmic-Competitive Algorithm for the k-Server Problem | Nikhil Bansal, IBM Research Niv Buchbinder, Open University Aleksander Mądry, Massachusetts Institute of Technology Joseph Naor, Technion |
| 2011 | Approximating Graphic TSP by Matchings | Tobia M¨o;mke & Ola Svensson, Royal Institute of Technology |
| 2010 | Approximation Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions | Matthew Andrews, Bell Labs |
| 2010 | Subexponential Algorithms for Unique Games and Related Problems | Sanjeev Arora, Princeton University Boaz Barak, Princeton University David Steurer, Princeton University |
| 2010 | Computational Transition at the Uniqueness Threshold | Allan Sly, Microsoft Research |
| 2008 | Two Query PCP with Sub-Constant Error | Dana Moshkovitz & Ran Raz, Weizmann Institute of Science |
| 2007 | Space-Efficient Identity Based Encryption Without Pairings | Dan Boneh, Stanford University Craig Gentry, Stanford University Michael Hamburg, Stanford University |
| 2006 | Settling the Complexity of 2-Player Nash Equilibrium | Xi Chen, Tsinghua University Xiaotie Deng, City University of Hong Kong |
| 2005 | The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into L1 | Subhash A. Khot, Georgia Institute of Technology Nisheeth K. Vishnoi, IBM Research |
| 2005 | Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time | Farzad Parvaresh & Alexander Vardy, University of California San Diego |
| 2004 | Cryptography in NC0 | Benny Applebaum, Technion Yuval Ishai, Technion Eyal Kushilevitz, Technion |
| 2004 | Hardness of Approximating the Shortest Vector Problem in Lattices | Subhash Khot, Georgia Institute of Technology |
| 2003 | On the Impossibility of Dimension Reduction in L1 | Bo Brinkman & Moses Charikar, Princeton University |
| 2002 | A Dichotomy Theorem for Constraints on a Three-Element Set | Andrei A. Bulatov, University of Oxford |
| 2002 | Minimizing Congestion in General Networks | Harald Räcke, Paderborn University |
| 2002 | Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model | Boaz Barak, Weizmann Institute of Science |
