FOCS 2016 - List of Accepted Papers



  • Robust Estimators in High Dimensions without the Computational Intractability

    Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart


  • Structure of protocols for XOR functions

    Hamed Hatami, Kaave Hosseini, Shachar Lovett


  • The multiparty communication complexity of interleaved group products

    Timothy Gowers, Emanuele Viola


  • Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning

    Ran Raz


  • An average-case depth hierarchy theorem for higher depths.

    Johan Hastad


  • 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


  • Commutativity in the Algorithmic Lovasz Local Lemma

    Vladimir Kolmogorov


  • Amplification and Derandomization Without Slowdown

    Ofer Grossman, Dana Moshkovitz


  • A PTAS for the Steiner Forest Problem in Doubling Metrics

    T-H. Hubert Chan, Shuguang Hu, Shaofeng H.-C. Jiang


  • Local Search Yields a PTAS for $k$-Means in Doubling Metrics

    Zachary Friggstad, Mohsen Rezapour, Mohammad Salavatipour


  • Depth reduction for composites

    Shiteng Chen, Periklis A. Papakonstantinou


  • Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-Uniform Distributions

    Sungjin Im, Shi Li


  • The Salesman's Improved Paths: A 3/2+1/34 Approximation

    Andras Sebo, Anke van Zuylen


  • Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols

    Eshan Chattopadhyay, Xin Li


  • Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering

    Fedor V. Fomin, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh


  • Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy

    Xin Li


  • Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics

    Amit Chakrabarti, Sagar Kale


  • A New Approach for Testing Properties of Discrete Distributions

    Ilias Diakonikolas, Daniel Kane


  • The Constant Inapproximability of the Parameterized Dominating Set Problem

    Yijia Chen, Bingkai Lin


  • 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 (Seffi) Naor, Debmalya Panigrahi


  • Rectangular Kronecker coefficients and plethysms in geometric complexity theory

    Christian Ikenmeyer, Greta Panova


  • Extractors for Near Logarithmic Min-Entropy

    Gil Cohen, Leonard J. Schulman


  • Making the Most of Advice: New Correlation Breakers and Their Applications

    Gil Cohen


  • Testing Assignments to Constraint Satisfaction Problems

    Hubie Chen, Matt Valeriote, Yuichi Yoshida


  • Heavy hitters via cluster-preserving clustering

    Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup


  • Edit Distance: Sketching, Streaming and Document Exchange

    Djamal Belazzougui, Qin Zhang


  • Accelerated Newton Iteration for Roots of Black Box Polynomials

    Anand Louis, Santosh S. Vempala


  • 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


  • Towards Strong Reverse Minkowski-type Inequalities

    Daniel Dadush, Oded Regev


  • Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication

    Omri Weinstein, Huacheng Yu


  • The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling

    Zachary Remscrim


  • A Discrete and Bounded Envy-free Cake Cutting Protocol for Any Number of Agents

    Haris Aziz, Simon Mackenzie


  • Linear Hashing is Awesome

    M. Knudsen


  • Which Regular Expression Patterns are Hard to Match?

    Arturs Backurs, Piotr Indyk


  • Zero-knowledge proof systems for QMA

    Anne Broadbent, Zhengfeng Ji, Fang Song, John Watrous


  • Decidability of Non-Interactive Simulation of Joint Distributions

    Badih Ghazi, Pritish Kamath, Madhu Sudan


  • Polynomial Representations of Threshold Functions and Algorithmic Applications

    Josh Alman, Timothy M. Chan, Ryan Williams


  • On Fully Dynamic Graph Sparsifiers

    Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, Richard Peng


  • 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


  • Max-Information, Differential Privacy, and Post-Selection Hypothesis Testing

    Ryan Rogers, Aaron Roth, Adam Smith, Om Thakkar


  • Computational Efficiency Requires Simple Taxation

    Shahar Dobzinski


  • Noisy population recovery in polynomial time.

    Anindya De, Michael Saks, Sijian Tang


  • The number of solutions for random regular NAE-SAT

    Allan Sly, Nike Sun, Yumeng Zhang


  • How to determine if a random graph with a fixed degree sequence has a giant component

    Felix Joos, Guillem Perarnau, Dieter Rautenbach, Bruce Reed


  • A deterministic polynomial time algorithm for non-commutative rational identity testing

    Ankit Garg, Leonid Gurvits, Rafael Oliveira, Avi Wigderson


  • Computing Maximum Flow with Augmenting Electrical Flows

    Aleksander Madry


  • Algorithm for Komlos conjecture: matching Banaszczyk's bound

    Nikhil Bansal, Daniel Dadush, Shashwat Garg


  • Fourier-sparse interpolation without a frequency gap

    Xue Chen, Daniel M. Kane, Eric Price, Zhao Song


  • No occurrence obstructions in geometric complexity theory

    Peter Burgisser, Christian Ikenmeyer, Greta Panova


  • Constrained Submodular Maximization: Beyond 1/e

    Alina Ene, Huy L Nguyen


  • Decremental Single-Source Reachability and Strongly Connected Components in $O(m\sqrt{n \log n})$ Total Update Time

    Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Lacki, Nikos Parotsidis


  • Informational Substitutes

    Yiling Chen, Bo Waggoner


  • Exponential Lower Bounds for Monotone Span Programs

    Robert Robere, Toniann Pitassi, Benjamin Rossman, Stephen A. Cook


  • A New Framework for Distributed Submodular Maximization

    Rafael da Ponte Barbosa, Alina Ene, Huy L Nguyen, Justin Ward


  • On Approximating Maximum Independent Set of Rectangles

    Julia Chuzhoy, Alina Ene


  • Ramanujan Graphs in Polynomial Time

    Michael B. Cohen


  • Optimal Quantile Approximation in Streams

    Zohar Karnin, Kevin Lang, Edo Liberty


  • Bounded-Communication Leakage Resilience via Parity-Resilient Circuits

    Vipul Goyal, Yuval Ishai, Hemanta K. Maji, Amit Sahai, Alexander Sherstov


  • NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem

    Venkata Gandikota, Badih Ghazi, Elena Grigorescu


  • Hopsets with Constant Hopbound, and Applications to Approximate Shortest-Paths

    Michael Elkin, Ofer Neiman


  • Settling the complexity of computing approximate two-player Nash equilibria

    Aviad Rubinstein


  • A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

    Boaz Barak, Samuel B.Hopkins, Jonathan Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin


  • Separations in communication complexity using cheat sheets and information complexity

    Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Goos, Robin Kothari, Rahul Jain, Troy Lee, Miklos Santha


  • Compressing Interactive Communication under Product Distributions

    Alexander A. Sherstov


  • Agnostic Estimation of Mean and Covariance

    Kevin Lai, Anup Rao, Santosh Vempala


  • An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model

    Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie


  • Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple

    Rasmus Kyng, Sushant Sachdeva


  • Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing

    Elizabeth Crosson, Aram Harrow


  • Robust Fourier and Polynomial Curve Fitting

    Venkatesan Guruswami, David Zuckerman


  • 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


  • How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)

    Susanna F. de Rezende, Jakob Nordstrom, Marc Vinyals


  • Fully Dynamic Maximal Matching in Constant Update Time

    Shay Solomon


  • Universal Simulation of Directed Systems in the abstract Tile Assembly Model Requires Undirectedness

    Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers, Matthew Patitz


  • Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism

    Sofya Raskhodnikova, Adam Smith


  • Local Conflict Coloring

    Pierre Fraigniaud, Marc Heinrich, Adrian Kosowski


  • Learning in Auctions: Regret is Hard, Envy is Easy

    Constantinos Daskalakis, Vasilis Syrgkanis


  • Polynomial-time tensor decompositions with sum-of-squares

    Tengyu Ma, Jonathan Shi, David Steurer


  • Faster and Simpler Network (Un)reliability Estimation

    David Karger


  • Extension Complexity of Independent Set Polytopes

    Mika Goos, Rahul Jain, Thomas Watson


  • Indistinguishability Obfuscation from DDH-like Assumptions on Constant-Degree Graded Encodings

    Huijia Lin, Vinod Vaikuntanathan


  • Optimizing Star-Convex Functions

    Jasper C.H. Lee, Paul Valiant


  • Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms

    Amir Abboud, Soren Dahlgaard


  • Breaking the Three Round Barrier for Non-Malleable Commitments

    Vipul Goyal, Dakshita Khurana, Amit Sahai


  • Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More

    Michael B. Cohen, Jonathan Kelner, Richard Peng, John Peebles, Aaron Sidford, Adrian Vladu