FOCS 2016 Program


Compressed Zip File of the FOCS Program and Proceedings


Saturday, October 8, 2016



- 8:00 pm

Welcome Reception - Brunswick Ballroom





Sunday, October 9, 2016



- 8:45

Continental Breakfast - Prefunction (outside Garden State)



Session 1.1a - Regency BC

Session 1.1b - Garden State ABC


- 9:20

Bounded-Communication Leakage Resilience via Parity-Resilient Circuits

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



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

Amit Chakrabarti, Sagar Kale


- 9:45

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

Edit Distance: Sketching, Streaming and Document Exchange



Huijia Lin, Vinod Vaikuntanathan

Djamal Belazzougui, Qin Zhang


- 10:10

Breaking the Three Round Barrier for Non-Malleable Commitments

Heavy Hitters via Cluster-preserving Clustering



Vipul Goyal, Dakshita Khurana, Amit Sahai

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


- 10:35

Zero-knowledge Proof Systems for QMA

Optimal Quantile Approximation in Streams



Anne Broadbent, Zhengfeng Ji, Fang Song, John Watrous

Zohar Karnin, Kevin Lang, Edo Liberty


- 10:55

Coffee Break - Prefunction (outside Garden State)



Session 1.2a - Regency BC

Session 1.2b - Garden State ABC


- 11:15

An Average-case Depth Hierarchy Theorem for Higher Depths

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



Johan Hastad

Andras Sebo, Anke van Zuylen


- 11:40

A Better-than-3n Lower Bound for the Circuit Complexity of an Explicit Function

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



Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov

Michael Elkin, Ofer Neiman


- 12:05

Depth Reduction for Composites

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



Shiteng Chen, Periklis A. Papakonstantinou

Sungjin Im, Shi Li


- 12:30

A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing

Online Algorithms for Covering and Packing Problems with Convex Objectives



Ankit Garg, Leonid Gurvits, Rafael Oliveira, Avi Wigderson

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


- 2:30

Lunch - Regency DEF



Session 1.3a - Regency BC

Session 1.3b - Garden State ABC


- 2:50

Extractors for Near Logarithmic Min-Entropy

Computational Efficiency Requires Simple Taxation



Gil Cohen, Leonard J. Schulman

Shahar Dobzinski


- 3:15

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

Learning in Auctions: Regret is Hard, Envy is Easy



Gil Cohen

Constantinos Daskalakis, Vasilis Syrgkanis


- 3:40

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

On the Communication Complexity of Approximate Fixed Points



Eshan Chattopadhyay, Xin Li

Tim Roughgarden, Omri Weinstein


- 4:05

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

Informational Substitutes



Xin Li

Yiling Chen, Bo Waggoner


- 4:30

The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling

Constrained Submodular Maximization: Beyond 1/e



Zachary Remscrim

Alina Ene, Huy L Nguyen


- 4:40

Coffee Break - Prefunction (outside Garden State)



Session 1.4 - Regency BC


- 5:00

Settling the Complexity of Computing Approximate Two-player Nash Equilibria



Aviad Rubinstein



- 5:25

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



Ran Raz



- 5:50

Ramanujan Graphs in Polynomial Time



Michael B. Cohen




Business Meeting - Regency BC





Monday, October 10, 2016



- 8:45

Continental Breakfast - Prefunction (outside Garden State)



Session 2.1a - Regency BC

Session 2.1b - Garden State ABC


- 9:20

Structure of Protocols for XOR Functions

Decremental Single-Source Reachability and Strongly Connected Components in Õ(m √n) Total Update Time



Hamed Hatami, Kaave Hosseini, Shachar Lovett

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


- 9:45

The Multiparty Communication Complexity of Interleaved Group Product

Fully Dynamic Maximal Matching in Constant Update Time



Timothy Gowers, Emanuele Viola

Shay Solomon


- 10:10

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

On Fully Dynamic Graph Sparsifiers



Susanna F. de Rezende, Jakob Nordström, Marc Vinyals


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


- 10:35

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

Linear Hashing is Awesome



Omri Weinstein, Huacheng Yu

Mathias Bæk Tejs Knudsen


- 10:55

Coffee Break - Prefunction (outside Garden State)



Session 2.2 - Regency BC


- 11:15

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



- 11:35

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



Zachary Friggstad, Mohsen Rezapour, Mohammad Salavatipour



- 11:55

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




Session 2.3 - Regency BC


- 1:00

Knuth Prize Lecture



Noam Nisan, Hebrew University of Jerusalem



- 2:30

Lunch - Brunswick



Session 2.4 - Regency BC


- 2:50

No Occurrence Obstructions in Geometric Complexity Theory



Peter Bürgisser, Christian Ikenmeyer, Greta Panova





Rectangular Kronecker Coefficients and Plethysms in Geometric Complexity Theory



Christian Ikenmeyer, Greta Panova



- 3:15

Exponential Lower Bounds for Monotone Span Programs



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



- 3:40

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



Haris Aziz, Simon Mackenzie



- 3:55

Coffee Break - Prefunction (outside Garden State)



Session 2.5a - Regency BC

Session 2.5b - Garden State ABC


- 4:15

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

Which Regular Expression Patterns are Hard to Match?



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

Arturs Backurs, Piotr Indyk


- 4:40

Polynomial-time Tensor Decompositions with Sum-of-squares

Polynomial Representations of Threshold Functions with Applications



Tengyu Ma, Jonathan Shi, David Steurer

Josh Alman, Timothy M. Chan, Ryan Williams


- 5:05

Towards Strong Reverse Minkowski-type Inequalities

Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms



Daniel Dadush, Oded Regev

Amir Abboud, Sogren Dahlgaard


- 5:20

Coffee Break - Prefunction (outside Garden State)



Session 2.6a - Regency BC

Session 2.6b - Garden State ABC


- 5:40

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

The Constant Inapproximability of the Parameterized Dominating Set Problem



Ryan Rogers, Aaron Roth, Adam Smith, Om Thakkar

Yijia Chen, Bingkai Lin


- 6:05

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

Subexponential Parameterized Algorithms for Planar and Apex-minor-free Graphs via Low Treewidth Pattern Covering



Sofya Raskhodnikova, Adam Smith

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


- 6:30


Testing Assignments to Constraint Satisfaction Problems




Hubie Chen, Matt Valeriote, Yuichi Yoshida





Tuesday, October 11, 2016



- 8:45

Continental Breakfast - Prefunction (outside Garden State)



Session 3.1a - Regency BC

Session 3.1b - Garden State ABC


- 9:20

Compressing Interactive Communication under
Product Distributions

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



Alexander A. Sherstov

Rasmus Kyng, Sushant Sachdeva


- 9:45

Decidability of Non-Interactive Simulation of Joint Distributions

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



Badih Ghazi, Pritish Kamath, Madhu Sudan

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


- 10:10

Separations in Communication Complexity using Cheat Sheets and Information Complexity

Computing Maximum Flow with Augmenting Electrical Flows



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

Aleksander Madry


- 10:35

Extension Complexity of Independent Set Polytopes

Optimizing Star-Convex Functions



Mika Göös, Rahul Jain, Thomas Watson

Jasper C.H. Lee, Paul Valiant


- 10:55

Coffee Break - Prefunction (outside Garden State)



Session 3.2a - Regency BC

Session 3.2b - Garden State ABC


- 11:15

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

Robust Estimators in High Dimensions without the Computational Intractability



Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie

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


- 11:40

Local Conflict Coloring

Agnostic Estimation of Mean and Covariance



Pierre Fraigniaud, Marc Heinrich, Adrian Kosowski

Kevin Lai, Anup Rao, Santosh Vempala


- 12:05

A Fast and Simple Unbiased Estimator for Network (Un)reliability

Noisy Population Recovery in Polynomial Time



David Karger

Anindya De, Michael Saks, Sijian Tang


- 12:30

A New Framework for Distributed Submodular Maximization

A New Approach for Testing Properties of Discrete Distributions



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

Ilias Diakonikolas, Daniel Kane


- 2:30

Lunch - Brunswick



Session 3.3a - Regency BC

Session 3.3b - Garden State ABC


- 2:50

How to Determine if a Random Graph with a Fixed Degree Sequence has a Giant Component

Accelerated Newton Iteration for Roots of Black Box Polynomials



Felix Joos, Guillem Perarnau, Dieter Rautenbach, Bruce Reed

Anand Louis, Santosh S. Vempala


- 3:15

Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model

Fourier-sparse Interpolation without a Frequency Gap



Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda, Yitong Yin

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


- 3:40

Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing

Robust Fourier and Polynomial Curve Fitting



Elizabeth Crosson, Aram Harrow

Venkatesan Guruswami, David Zuckerman


- 4:05

The Number of Solutions for Random Regular NAE-SAT

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



Allan Sly, Nike Sun, Yumeng Zhang

Venkata Gandikota, Badih Ghazi, Elena Grigorescu


- 4:25

Coffee Break - Prefunction (outside Garden State)



Session 3.4a - Regency BC

Session 3.4b - Garden State ABC


- 4:45

Amplification and Derandomization Without Slowdown

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



Ofer Grossman, Dana Moshkovitz

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


- 5:10

Commutativity in the Algorithmic Lovasz Local Lemma

A PTAS for the Steiner Forest Problem in Doubling Metrics



Vladimir Kolmogorov

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


- 5:35

Algorithm for Komlós Conjecture: Matching Banaszczyk's Bound

On Approximating Maximum Independent Set of Rectangles



Nikhil Bansal, Daniel Dadush, Shashwat Garg

Julia Chuzhoy, Alina Ene