| 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 | A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing. Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson |
| 2016 | A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents. Haris Aziz, Simon Mackenzie |
| 2016 | A Fast and Simple Unbiased Estimator for Network (Un)reliability. David R. Karger |
| 2016 | A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin |
| 2016 | A New Approach for Testing Properties of Discrete Distributions. Ilias Diakonikolas, Daniel M. Kane |
| 2016 | A New Framework for Distributed Submodular Maximization. Rafael da Ponte Barbosa, Alina Ene, Huy L. Nguyen, Justin Ward |
| 2016 | A PTAS for the Steiner Forest Problem in Doubling Metrics. T.-H. Hubert Chan, Shuguang Hu, Shaofeng H.-C. Jiang |
| 2016 | Accelerated Newton Iteration for Roots of Black Box Polynomials. Anand Louis, Santosh S. Vempala |
| 2016 | Agnostic Estimation of Mean and Covariance. Kevin A. Lai, Anup B. Rao, Santosh S. Vempala |
| 2016 | Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication. Omri Weinstein, Huacheng Yu |
| 2016 | Amplification and Derandomization without Slowdown. Ofer Grossman, Dana Moshkovitz |
| 2016 | An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound. Nikhil Bansal, Daniel Dadush, Shashwat Garg |
| 2016 | An Average-Case Depth Hierarchy Theorem for Higher Depth. Johan Håstad |
| 2016 | An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie |
| 2016 | Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple. Rasmus Kyng, Sushant Sachdeva |
| 2016 | Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-uniform Distributions. Sungjin Im, Shi Li |
| 2016 | Bounded-Communication Leakage Resilience via Parity-Resilient Circuits. Vipul Goyal, Yuval Ishai, Hemanta K. Maji, Amit Sahai, Alexander A. Sherstov |
| 2016 | Breaking the Three Round Barrier for Non-malleable Commitments. Vipul Goyal, Dakshita Khurana, Amit Sahai |
| 2016 | Commutativity in the Algorithmic Lovász Local Lemma. Vladimir Kolmogorov |
| 2016 | Compressing Interactive Communication under Product Distributions. Alexander A. Sherstov |
| 2016 | Computational Efficiency Requires Simple Taxation. Shahar Dobzinski |
| 2016 | Computing Maximum Flow with Augmenting Electrical Flows. Aleksander Madry |
| 2016 | Constrained Submodular Maximization: Beyond 1/e. Alina Ene, Huy L. Nguyen |
| 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 | Decidability of Non-interactive Simulation of Joint Distributions. Badih Ghazi, Pritish Kamath, Madhu Sudan |
| 2016 | Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time. Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Lacki, Nikos Parotsidis |
| 2016 | Depth-Reduction for Composites. Shiteng Chen, Periklis A. Papakonstantinou |
| 2016 | Edit Distance: Sketching, Streaming, and Document Exchange. Djamal Belazzougui, Qin Zhang |
| 2016 | Explicit Non-malleable Extractors, Multi-source Extractors, and Almost Optimal Privacy Amplification Protocols. Eshan Chattopadhyay, Xin Li |
| 2016 | Exponential Lower Bounds for Monotone Span Programs. Robert Robere, Toniann Pitassi, Benjamin Rossman, Stephen A. Cook |
| 2016 | Extension Complexity of Independent Set Polytopes. Mika Göös, Rahul Jain, Thomas Watson |
| 2016 | Extractors for Near Logarithmic Min-Entropy. Gil Cohen, Leonard J. Schulman |
| 2016 | Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. Ran Raz |
| 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 | Fourier-Sparse Interpolation without a Frequency Gap. Xue Chen, Daniel M. Kane, Eric Price, Zhao Song |
| 2016 | Fully Dynamic Maximal Matching in Constant Update Time. Shay Solomon |
| 2016 | Heavy Hitters via Cluster-Preserving Clustering. Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup |
| 2016 | Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. Michael Elkin, Ofer Neiman |
| 2016 | How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity). Susanna F. de Rezende, Jakob Nordström, Marc Vinyals |
| 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 | IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, Hyatt Regency, New Brunswick, New Jersey, USA, October 9-11, 2016 Irit Dinur |
| 2016 | Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy. Xin Li |
| 2016 | Indistinguishability Obfuscation from DDH-Like Assumptions on Constant-Degree Graded Encodings. Huijia Lin, Vinod Vaikuntanathan |
| 2016 | Informational Substitutes. Yiling Chen, Bo Waggoner |
| 2016 | Knuth Prize Lecture: Complexity of Communication in Markets. Noam Nisan |
| 2016 | Learning in Auctions: Regret is Hard, Envy is Easy. Constantinos Daskalakis, Vasilis Syrgkanis |
| 2016 | Linear Hashing Is Awesome. Mathias Bæk Tejs Knudsen |
| 2016 | Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism. Sofya Raskhodnikova, Adam D. Smith |
| 2016 | Local Conflict Coloring. Pierre Fraigniaud, Marc Heinrich, Adrian Kosowski |
| 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 | Local Search Yields a PTAS for k-Means in Doubling Metrics. Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour |
| 2016 | Making the Most of Advice: New Correlation Breakers and Their Applications. Gil Cohen |
| 2016 | Max-Information, Differential Privacy, and Post-selection Hypothesis Testing. Ryan M. Rogers, Aaron Roth, Adam D. Smith, Om Thakkar |
| 2016 | NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem. Venkata Gandikota, Badih Ghazi, Elena Grigorescu |
| 2016 | No Occurrence Obstructions in Geometric Complexity Theory. Peter Bürgisser, Christian Ikenmeyer, Greta Panova |
| 2016 | Noisy Population Recovery in Polynomial Time. Anindya De, Michael E. Saks, Sijian Tang |
| 2016 | On Approximating Maximum Independent Set of Rectangles. Julia Chuzhoy, Alina Ene |
| 2016 | On Fully Dynamic Graph Sparsifiers. Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, Richard Peng |
| 2016 | On the Communication Complexity of Approximate Fixed Points. Tim Roughgarden, Omri Weinstein |
| 2016 | Online Algorithms for Covering and Packing Problems with Convex Objectives. Yossi Azar, Niv Buchbinder, T.-H. Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph Naor, Debmalya Panigrahi |
| 2016 | Optimal Quantile Approximation in Streams. Zohar S. Karnin, Kevin J. Lang, Edo Liberty |
| 2016 | Optimizing Star-Convex Functions. Jasper C. H. Lee, Paul Valiant |
| 2016 | Polynomial Representations of Threshold Functions and Algorithmic Applications. Josh Alman, Timothy M. Chan, R. Ryan Williams |
| 2016 | Polynomial-Time Tensor Decompositions with Sum-of-Squares. Tengyu Ma, Jonathan Shi, David Steurer |
| 2016 | Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms. Amir Abboud, Søren Dahlgaard |
| 2016 | Ramanujan Graphs in Polynomial Time. Michael B. Cohen |
| 2016 | Rectangular Kronecker Coefficients and Plethysms in Geometric Complexity Theory. Christian Ikenmeyer, Greta Panova |
| 2016 | Robust Estimators in High Dimensions without the Computational Intractability. Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart |
| 2016 | Robust Fourier and Polynomial Curve Fitting. Venkatesan Guruswami, David Zuckerman |
| 2016 | Separations in Communication Complexity Using Cheat Sheets and Information Complexity. Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha |
| 2016 | Settling the Complexity of Computing Approximate Two-Player Nash Equilibria. Aviad Rubinstein |
| 2016 | Simulated Quaotum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing. Elizabeth Crosson, Aram W. Harrow |
| 2016 | Strong Fooling Sets for Multi-player Communication with Applications to Deterministic Estimation of Stream Statistics. Amit Chakrabarti, Sagar Kale |
| 2016 | Structure of Protocols for XOR Functions. Hamed Hatami, Kaave Hosseini, Shachar Lovett |
| 2016 | Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh |
| 2016 | Testing Assignments to Constraint Satisfaction Problems. Hubie Chen, Matthew Valeriote, Yuichi Yoshida |
| 2016 | The Constant Inapproximability of the Parameterized Dominating Set Problem. Yijia Chen, Bingkai Lin |
| 2016 | The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling. Zachary Remscrim |
| 2016 | The Multiparty Communication Complexity of Interleaved Group Products. W. T. Gowers, Emanuele Viola |
| 2016 | The Number of Solutions for Random Regular NAE-SAT. Allan Sly, Nike Sun, Yumeng Zhang |
| 2016 | The Salesman's Improved Paths: A 3/2+1/34 Approximation. András Sebö, Anke van Zuylen |
| 2016 | Towards Strong Reverse Minkowski-Type Inequalities for Lattices. Daniel Dadush, Oded Regev |
| 2016 | Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product. Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams |
| 2016 | Universal Simulation of Directed Systems in the Abstract Tile Assembly Model Requires Undirectedness. Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers |
| 2016 | Which Regular Expression Patterns Are Hard to Match? Arturs Backurs, Piotr Indyk |
| 2016 | Zero-Knowledge Proof Systems for QMA. Anne Broadbent, Zhengfeng Ji, Fang Song, John Watrous |