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