| 2016 | Separations in query complexity using cheat sheets. | Scott Aaronson, Shalev Ben-David, Robin Kothari |
| 2015 | Nearly-Linear Time Positive LP Solver with Faster Convergence Rate. | Zeyuan Allen Zhu, Lorenzo Orecchia |
| 2015 | Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates. | Zeyuan Allen Zhu, Zhenyu Liao, Lorenzo Orecchia |
| 2015 | Quantum Information Complexity. | Dave Touchette |
| 2015 | Faster Canonical Forms for Primitive Coherent Configurations: Extended Abstract. | Xiaorui Sun, John Wilmes |
| 2015 | Analysis of a Classical Matrix Preconditioning Algorithm. | Leonard J. Schulman, Alistair Sinclair |
| 2015 | Inapproximability of Nash Equilibrium. | Aviad Rubinstein |
| 2015 | Quantum Spectrum Testing. | Ryan O'Donnell, John Wright |
| 2015 | Randomized Rounding for the Largest Simplex Problem. | Aleksandar Nikolov |
| 2015 | Approximate k-flat Nearest Neighbor Search. | Wolfgang Mulzer, Huy L. Nguyn, Paul Seiferth, Yannik Stein |
| 2015 | Consistency Thresholds for the Planted Bisection Model. | Elchanan Mossel, Joe Neeman, Allan Sly |
| 2015 | Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices. | Ankur Moitra |
| 2015 | Randomized Composable Core-sets for Distributed Submodular Maximization. | Vahab S. Mirrokni, Morteza Zadimoghaddam |
| 2015 | Sum-of-squares Lower Bounds for Planted Clique. | Raghu Meka, Aaron Potechin, Avi Wigderson |
| 2015 | Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions. | Shachar Lovett, Jiapeng Zhang |
| 2015 | Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms. | Anand Louis |
| 2015 | FPTAS for #BIS with Degree Bounds on One Side. | Jingcheng Liu, Pinyan Lu |
| 2015 | Learning Arbitrary Statistical Mixtures of Discrete Distributions. | Jian Li, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy |
| 2015 | Lower Bounds on the Size of Semidefinite Programming Relaxations. | James R. Lee, Prasad Raghavendra, David Steurer |
| 2015 | Hardness of Graph Pricing Through Generalized Max-Dicut. | Euiwoong Lee |
| 2015 | Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms. | Kasper Green Larsen, Jelani Nelson, Huy L. Nguyn |
| 2015 | The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree. | Jakub Lacki, Jakub Ocwieja, Marcin Pilipczuk, Piotr Sankowski, Anna Zych |
| 2015 | Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract. | Pravesh K. Kothari, Raghu Meka |
| 2015 | Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order. | Nitish Korula, Vahab S. Mirrokni, Morteza Zadimoghaddam |
| 2015 | Indistinguishability Obfuscation for Turing Machines with Unbounded Memory. | Venkata Koppula, Allison Bishop Lewko, Brent Waters |