| 2016 | Computing Maximum Flow with Augmenting Electrical Flows. | Aleksander Madry |
| 2016 | Accelerated Newton Iteration for Roots of Black Box Polynomials. | Anand Louis, Santosh S. Vempala |
| 2016 | Indistinguishability Obfuscation from DDH-Like Assumptions on Constant-Degree Graded Encodings. | Huijia Lin, Vinod Vaikuntanathan |
| 2016 | Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy. | Xin Li |
| 2016 | Optimizing Star-Convex Functions. | Jasper C. H. Lee, Paul Valiant |
| 2016 | Heavy Hitters via Cluster-Preserving Clustering. | Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup |
| 2016 | Agnostic Estimation of Mean and Covariance. | Kevin A. Lai, Anup B. Rao, Santosh S. Vempala |
| 2016 | Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple. | Rasmus Kyng, Sushant Sachdeva |
| 2016 | Commutativity in the Algorithmic Lovsz Local Lemma. | Vladimir Kolmogorov |
| 2016 | Linear Hashing Is Awesome. | Mathias Bk Tejs Knudsen |
| 2016 | Optimal Quantile Approximation in Streams. | Zohar S. Karnin, Kevin J. Lang, Edo Liberty |
| 2016 | A Fast and Simple Unbiased Estimator for Network (Un)reliability. | David R. Karger |
| 2016 | How to Determine if a Random Graph with a Fixed Degree Sequence Has a Giant Component. | Felix Joos, Guillem Perarnau, Dieter Rautenbach, Bruce A. Reed |
| 2016 | Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-uniform Distributions. | Sungjin Im, Shi Li |
| 2016 | Rectangular Kronecker Coefficients and Plethysms in Geometric Complexity Theory. | Christian Ikenmeyer, Greta Panova |
| 2016 | Universal Simulation of Directed Systems in the Abstract Tile Assembly Model Requires Undirectedness. | Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers |
| 2016 | Structure of Protocols for XOR Functions. | Hamed Hatami, Kaave Hosseini, Shachar Lovett |
| 2016 | An Average-Case Depth Hierarchy Theorem for Higher Depth. | Johan Hstad |
| 2016 | Robust Fourier and Polynomial Curve Fitting. | Venkatesan Guruswami, David Zuckerman |
| 2016 | Amplification and Derandomization without Slowdown. | Ofer Grossman, Dana Moshkovitz |
| 2016 | Breaking the Three Round Barrier for Non-malleable Commitments. | Vipul Goyal, Dakshita Khurana, Amit Sahai |
| 2016 | Bounded-Communication Leakage Resilience via Parity-Resilient Circuits. | Vipul Goyal, Yuval Ishai, Hemanta K. Maji, Amit Sahai, Alexander A. Sherstov |
| 2016 | The Multiparty Communication Complexity of Interleaved Group Products. | W. T. Gowers, Emanuele Viola |
| 2016 | Extension Complexity of Independent Set Polytopes. | Mika Gs, Rahul Jain, Thomas Watson |
| 2016 | Decidability of Non-interactive Simulation of Joint Distributions. | Badih Ghazi, Pritish Kamath, Madhu Sudan |