| 2017 | Testing Hereditary Properties of Ordered Graphs and Matrices. | Noga Alon, Omri Ben-Eliezer, Eldar Fischer |
| 2017 | Much Faster Algorithms for Matrix Scaling. | Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson |
| 2017 | First Efficient Convergence for Streaming k-PCA: A Global, Gap-Free, and Near-Optimal Rate. | Zeyuan Allen-Zhu, Yuanzhi Li |
| 2017 | Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms. | Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, Justin Ward |
| 2017 | Optimal Las Vegas Locality Sensitive Data Structures. | Thomas Dybdahl Ahle |
| 2017 | Distributed PCP Theorems for Hardness of Approximation in P. | Amir Abboud, Aviad Rubinstein, R. Ryan Williams |
| 2017 | Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve. | Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Knnemann |
| 2017 | On Learning Mixtures of Well-Separated Gaussians. | Oded Regev, Aravindan Vijayaraghavan |
| 2017 | The Ising Partition Function: Zeros and Deterministic Approximation. | Jingcheng Liu, Alistair Sinclair, Piyush Srivastava |
| 2017 | Learning Multi-Item Auctions with (or without) Samples. | Yang Cai, Constantinos Daskalakis |
| 2016 | Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication. | Omri Weinstein, Huacheng Yu |
| 2016 | Fully Dynamic Maximal Matching in Constant Update Time. | Shay Solomon |
| 2016 | The Number of Solutions for Random Regular NAE-SAT. | Allan Sly, Nike Sun, Yumeng Zhang |
| 2016 | Compressing Interactive Communication under Product Distributions. | Alexander A. Sherstov |
| 2016 | The Salesman's Improved Paths: A 3/2+1/34 Approximation. | Andrs Seb, Anke van Zuylen |
| 2016 | Settling the Complexity of Computing Approximate Two-Player Nash Equilibria. | Aviad Rubinstein |
| 2016 | On the Communication Complexity of Approximate Fixed Points. | Tim Roughgarden, Omri Weinstein |
| 2016 | Max-Information, Differential Privacy, and Post-selection Hypothesis Testing. | Ryan M. Rogers, Aaron Roth, Adam D. Smith, Om Thakkar |
| 2016 | Exponential Lower Bounds for Monotone Span Programs. | Robert Robere, Toniann Pitassi, Benjamin Rossman, Stephen A. Cook |
| 2016 | How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity). | Susanna F. de Rezende, Jakob Nordstrm, Marc Vinyals |
| 2016 | The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling. | Zachary Remscrim |
| 2016 | Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. | Ran Raz |
| 2016 | Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism. | Sofya Raskhodnikova, Adam D. Smith |
| 2016 | Knuth Prize Lecture: Complexity of Communication in Markets. | Noam Nisan |
| 2016 | Polynomial-Time Tensor Decompositions with Sum-of-Squares. | Tengyu Ma, Jonathan Shi, David Steurer |