| Year | Title | Authors |
|---|---|---|
| 2018 | A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem | Ola Svensson, École Polytechnique Fédérale de Lausanne Jakub Tarnawski, École Polytechnique Fédérale de Lausanne László A. Végh, London School of Economics |
| 2017 | Explicit, Almost Optimal, Epsilon-Balanced Codes | Amnon Ta-Shma, Tel-Aviv University |
| 2017 | A Weighted Linear Matroid Parity Algorithm | Satoru Iwata, University of Tokyo Yusuke Kobayashi, University of Tsukuba |
| 2017 | Deciding Parity Games in Quasipolynomial Time | Cristian S. Calude, University of Auckland Sanjay Jain, National University of Singapore Bakhadyr Khoussainov, University of Auckland Wei Li, National University of Singapore Frank Stephan, National University of Singapore |
| 2016 | Explicit Two-Source Extractors and Resilient Functions | Eshan Chattopadhyay & David Zuckerman, University of Texas at Austin |
| 2016 | Graph Isomorphism in Quasipolynomial Time | László Babaí, University of Chicago |
| 2016 | Reed-Muller Codes Achieve Capacity on Erasure Channels | Shrinivas Kudekar, Qualcomm Research Santhosh Kumar, Texas A&M University Marco Mondelli, École Polytechnique Fédérale de Lausanne Henry D. Pfister, Duke University Eren Sasoglu, Intel Rudiger Urbanke, École Polytechnique Fédérale de Lausanne |
| 2015 | Exponential Separation of Information and Communication for Boolean Functions | Anat Ganor, Weizmann Institute of Science Gillat Kol, Princeton University Ran Raz, Weizmann Institute of Science |
| 2015 | 2-Server PIR with sub-polynomial communication | Zeev Dvir & Sivakanth Gopi, Princeton University |
| 2015 | Lower Bounds on the Size of Semidefinite Programming Relaxations | James R. Lee, University of Washington Prasad Raghavendra, University of California Berkeley David Steurer, Cornell University |
| 2014 | The matching polytope has exponential extension complexity | Thomas Rothvoß, University of Washington |
| 2013 | Approximation Resistance from Pairwise Independent Subgroups | Siu On Chan, University of California Berkeley |
| 2013 | Low Rank Approximation and Regression in Input Sparsity Time | Kenneth L. Clarkson & David P. Woodruff, IBM Research |
| 2012 | Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds | Samuel Fiorini, Université libre de Bruxelles Serge Massar, Université libre de Bruxelles Sebastian Pokutta, Universität Erlangen Nürnberg Hans Tiwary, Université libre de Bruxelles Ronald de Wolf, Centrum Wiskunde & Informatica |
| 2012 | The Cell Probe Complexity of Dynamic Range Counting | Kasper Larsen, Aarhus University |
| 2011 | Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs | Paul Christiano, Massachusetts Institute of Technology Jonathan A. Kelner, Massachusetts Institute of Technology Aleksander Mądry, Massachusetts Institute of Technology Daniel A. Spielman, Yale University Shang-Hua Teng, University of Southern California |
| 2011 | Subexponential lower bounds for randomized pivoting rules for the simplex algorithm | Oliver Friedmann, University of Munich Thomas Dueholm Hansen, Aarhus University Uri Zwick, Tel-Aviv University |
| 2010 | An improved LP-based approximation for steiner tree | Jaroslaw Byrka, École Polytechnique Fédérale de Lausanne Fabrizio Grandoni, University of Tor Vergata Thomas Rothvoß, École Polytechnique Fédérale de Lausanne Laura Sanità, École Polytechnique Fédérale de Lausanne |
| 2010 | QIP = PSPACE | Rahul Jain, National University of Singapore Zhengfeng Ji, Perimeter Institute for Theoretical Physics Sarvagya Upadhyay, University of Waterloo John Watrous, University of Waterloo |
| 2009 | A constructive proof of the Lovász local lemma | Robin A. Moser, ETH Zurich |
| 2009 | Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem | Chris Peikert, SRI International |
| 2008 | Optimal algorithms and inapproximability results for every CSP? | Prasad Raghavendra, University of Washington |
| 2008 | Optimal hierarchical decompositions for congestion minimization in networks | Harald Räcke, University of Warwick |
| 2007 | Faster integer multiplication | Martin Fürer, Pennsylvania State University |
| 2007 | Towards 3-query locally decodable codes of subexponential length | Sergey Yekhanin, Massachusetts Institute of Technology |
| 2006 | The PCP theorem by gap amplification | Irit Dinur, Hebrew University |
| 2005 | Undirected ST-connectivity in log-space | Omer Reingold, Weizmann Institute of Science |
| 2004 | Multi-linear formulas for permanent and determinant are of super-polynomial size | Ran Raz, Weizmann Institute of Science |
| 2004 | Expander flows, geometric embeddings and graph partitioning | Sanjeev Arora, Princeton University Satish Rao, University of California Berkeley Umesh Vazirani, University of California Berkeley |
| 2003 | Derandomizing polynomial identity tests means proving circuit lower bounds | Valentine Kabanets & Russell Impagliazzo, University of California San Diego |
| 2003 | New lattice-based cryptographic constructions | Oded Regev, Tel-Aviv University |
