| 2017 | Local max-cut in smoothed polynomial time. | Omer Angel, Sbastien Bubeck, Yuval Peres, Fan Wei |
| 2017 | Approximate near neighbors for general symmetric norms. | Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten |
| 2017 | A generalization of permanent inequalities and applications in counting and optimization. | Nima Anari, Shayan Oveis Gharan |
| 2017 | Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. | Andris Ambainis, Martins Kokainis |
| 2017 | Probabilistic rank and matrix rigidity. | Josh Alman, R. Ryan Williams |
| 2017 | Finding approximate local minima faster than gradient descent. | Naman Agarwal, Zeyuan Allen Zhu, Brian Bullins, Elad Hazan, Tengyu Ma |
| 2017 | Beating 1-1/e for ordered prophets. | Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Robert D. Kleinberg, Brendan Lucier |
| 2017 | The computational complexity of ball permutations. | Scott Aaronson, Adam Bouland, Greg Kuperberg, Saeed Mehraban |
| 2017 | A reverse Minkowski theorem. | Oded Regev, Noah Stephens-Davidowitz |
| 2016 | A tight space bound for consensus. | Leqi Zhu |
| 2016 | Cell-probe lower bounds for dynamic problems via a new communication model. | Huacheng Yu |
| 2016 | Base collapse of holographic algorithms. | Mingji Xia |
| 2016 | Instance optimal learning of discrete distributions. | Gregory Valiant, Paul Valiant |
| 2016 | Efficiently decoding Reed-Muller codes from random errors. | Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk |
| 2016 | Beyond matroids: secretary problem and prophet inequality with general constraints. | Aviad Rubinstein |
| 2016 | Watch and learn: optimizing from revealed preferences feedback. | Aaron Roth, Jonathan R. Ullman, Zhiwei Steven Wu |
| 2016 | Constant-round interactive proofs for delegating computation. | Omer Reingold, Guy N. Rothblum, Ron D. Rothblum |
| 2016 | Weighted low rank approximations with provable guarantees. | Ilya P. Razenshteyn, Zhao Song, David P. Woodruff |
| 2016 | Poly-logarithmic Frege depth lower bounds via an expander switching lemma. | Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan |
| 2016 | Efficient quantum tomography. | Ryan O'Donnell, John Wright |
| 2016 | Maximizing determinants under partition constraints. | Aleksandar Nikolov, Mohit Singh |
| 2016 | Semidefinite programs on sparse random graphs and their application to community detection. | Andrea Montanari, Subhabrata Sen |
| 2016 | How robust are reconstruction thresholds for community detection? | Ankur Moitra, William Perry, Alexander S. Wein |
| 2016 | On approximating functions of the singular values in a stream. | Yi Li, David P. Woodruff |
| 2016 | A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies. | Elaine Levey, Thomas Rothvoss |