| 2016 | Sparsified Cholesky and multigrid solvers for connection laplacians. | Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Daniel A. Spielman |
| 2016 | Reed-Muller codes achieve capacity on erasure channels. | Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Sasoglu, Rdiger L. Urbanke |
| 2016 | High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. | Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf |
| 2016 | Interactive compression for product distributions. | Gillat Kol |
| 2016 | Candidate hard unique game. | Subhash Khot, Dana Moshkovitz |
| 2016 | On the size of homogeneous and of depth four formulas with low individual degree. | Neeraj Kayal, Chandan Saha, Sbastien Tavenas |
| 2016 | Enumerating parametric global minimum cuts by random interleaving. | David R. Karger |
| 2016 | Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time. | Michael Kapralov |
| 2016 | Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. | Daniel M. Kane, Ryan Williams |
| 2016 | Classical verification of quantum proofs. | Zhengfeng Ji |
| 2016 | Do prices coordinate markets? | Justin Hsu, Jamie Morgenstern, Ryan M. Rogers, Aaron Roth, Rakesh Vohra |
| 2016 | Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. | Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer |
| 2016 | A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. | Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai |
| 2016 | The computational power of optimization in online learning. | Elad Hazan, Tomer Koren |
| 2016 | Distributed (∆+1)-coloring in sublogarithmic rounds. | David G. Harris, Johannes Schneider, Hsin-Hao Su |
| 2016 | Ramanujan coverings of graphs. | Chris Hall, Doron Puder, William F. Sawin |
| 2016 | Sample-optimal tomography of quantum states. | Jeongwan Haah, Aram W. Harrow, Zheng-Feng Ji, Xiaodi Wu, Nengkun Yu |
| 2016 | Repairing Reed-solomon codes. | Venkatesan Guruswami, Mary Wootters |
| 2016 | Textbook non-malleable commitments. | Vipul Goyal, Omkant Pandey, Silas Richelson |
| 2016 | Matrix rigidity of random toeplitz matrices. | Oded Goldreich, Avishay Tal |
| 2016 | Entangled simultaneity versus classical interactivity in communication complexity. | Dmitry Gavinsky |
| 2016 | Exponential separation of communication and external information. | Anat Ganor, Gillat Kol, Ran Raz |
| 2016 | Separating subadditive euclidean functionals. | Alan M. Frieze, Wesley Pegden |
| 2016 | Parallel exhaustive search without coordination. | Pierre Fraigniaud, Amos Korman, Yoav Rodeh |
| 2016 | Exact algorithms via monotone local search. | Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, Saket Saurabh |