| 2016 | A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing. | Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson |
| 2016 | NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem. | Venkata Gandikota, Badih Ghazi, Elena Grigorescu |
| 2016 | Local Search Yields a PTAS for k-Means in Doubling Metrics. | Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour |
| 2016 | Local Conflict Coloring. | Pierre Fraigniaud, Marc Heinrich, Adrian Kosowski |
| 2016 | Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. | Fedor V. Fomin, Daniel Lokshtanov, Dniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh |
| 2016 | A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function. | Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov |
| 2016 | Constrained Submodular Maximization: Beyond 1/e. | Alina Ene, Huy L. Nguyen |
| 2016 | Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. | Michael Elkin, Ofer Neiman |
| 2016 | Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model. | Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda, Yitong Yin |
| 2016 | Computational Efficiency Requires Simple Taxation. | Shahar Dobzinski |
| 2016 | Robust Estimators in High Dimensions without the Computational Intractability. | Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart |
| 2016 | A New Approach for Testing Properties of Discrete Distributions. | Ilias Diakonikolas, Daniel M. Kane |
| 2016 | Noisy Population Recovery in Polynomial Time. | Anindya De, Michael E. Saks, Sijian Tang |
| 2016 | Learning in Auctions: Regret is Hard, Envy is Easy. | Constantinos Daskalakis, Vasilis Syrgkanis |
| 2016 | Towards Strong Reverse Minkowski-Type Inequalities for Lattices. | Daniel Dadush, Oded Regev |
| 2016 | Simulated Quaotum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing. | Elizabeth Crosson, Aram W. Harrow |
| 2016 | Extractors for Near Logarithmic Min-Entropy. | Gil Cohen, Leonard J. Schulman |
| 2016 | Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More. | Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, Adrian Vladu |
| 2016 | Ramanujan Graphs in Polynomial Time. | Michael B. Cohen |
| 2016 | Making the Most of Advice: New Correlation Breakers and Their Applications. | Gil Cohen |
| 2016 | Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. | Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu |
| 2016 | On Approximating Maximum Independent Set of Rectangles. | Julia Chuzhoy, Alina Ene |
| 2016 | Informational Substitutes. | Yiling Chen, Bo Waggoner |
| 2016 | Testing Assignments to Constraint Satisfaction Problems. | Hubie Chen, Matthew Valeriote, Yuichi Yoshida |
| 2016 | Depth-Reduction for Composites. | Shiteng Chen, Periklis A. Papakonstantinou |