FOCS 2016 Program

 

Compressed Zip File of the FOCS Program and Proceedings

 

Saturday, October 8, 2016

 

6:30 

- 8:00 pm

Welcome Reception - Brunswick Ballroom

 

 

 

 

Sunday, October 9, 2016

 

7:30 

- 8:45

Continental Breakfast - Prefunction (outside Garden State)

 

 

Session 1.1a - Regency BC

Session 1.1b - Garden State ABC

9:00 

- 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:25 

- 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

9:50 

- 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:15 

- 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:35 

- 10:55

Coffee Break - Prefunction (outside Garden State)

 

 

Session 1.2a - Regency BC

Session 1.2b - Garden State ABC

10:55 

- 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:20 

- 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

11:45 

- 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:10 

- 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

12:30 

- 2:30

Lunch - Regency DEF

 

 

Session 1.3a - Regency BC

Session 1.3b - Garden State ABC

2:30 

- 2:50

Extractors for Near Logarithmic Min-Entropy

Computational Efficiency Requires Simple Taxation

 

 

Gil Cohen, Leonard J. Schulman

Shahar Dobzinski

2:55 

- 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:20 

- 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

3:45 

- 4:05

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

Informational Substitutes

 

 

Xin Li

Yiling Chen, Bo Waggoner

4:10 

- 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:30 

- 4:40

Coffee Break - Prefunction (outside Garden State)

 

 

Session 1.4 - Regency BC

4:40 

- 5:00

Settling the Complexity of Computing Approximate Two-player Nash Equilibria

 

 

Aviad Rubinstein

 

5:05 

- 5:25

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

 

 

Ran Raz

 

5:30  

- 5:50

Ramanujan Graphs in Polynomial Time

 

 

Michael B. Cohen

 

8:30 

 

Business Meeting - Regency BC

 

 

 

 

Monday, October 10, 2016

 

7:30 

- 8:45

Continental Breakfast - Prefunction (outside Garden State)

 

 

Session 2.1a - Regency BC

Session 2.1b - Garden State ABC

9:00 

- 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:25 

- 9:45

The Multiparty Communication Complexity of Interleaved Group Product

Fully Dynamic Maximal Matching in Constant Update Time

 

 

Timothy Gowers, Emanuele Viola

Shay Solomon

9:50 

- 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:15 

- 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:35 

- 10:55

Coffee Break - Prefunction (outside Garden State)

 

 

Session 2.2 - Regency BC

10:55 

- 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:15 

- 11:35

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

 

 

Zachary Friggstad, Mohsen Rezapour, Mohammad Salavatipour

 

11:35 

- 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

12:00 

- 1:00

Knuth Prize Lecture

 

 

Noam Nisan, Hebrew University of Jerusalem

 

1:00 

- 2:30

Lunch - Brunswick

 

 

Session 2.4 - Regency BC

2:30 

- 2:50

No Occurrence Obstructions in Geometric Complexity Theory

 

 

Peter Bürgisser, Christian Ikenmeyer, Greta Panova

and

 

 

 

Rectangular Kronecker Coefficients and Plethysms in Geometric Complexity Theory

 

 

Christian Ikenmeyer, Greta Panova

 

2:55 

- 3:15

Exponential Lower Bounds for Monotone Span Programs

 

 

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

 

3:20 

- 3:40

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

 

 

Haris Aziz, Simon Mackenzie

 

3:40 

- 3:55

Coffee Break - Prefunction (outside Garden State)

 

 

Session 2.5a - Regency BC

Session 2.5b - Garden State ABC

3:55 

- 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:20 

- 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

4:45 

- 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:05 

- 5:20

Coffee Break - Prefunction (outside Garden State)

 

 

Session 2.6a - Regency BC

Session 2.6b - Garden State ABC

5:20 

- 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

5:45 

- 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:10 

- 6:30

 

Testing Assignments to Constraint Satisfaction Problems

 

 

 

Hubie Chen, Matt Valeriote, Yuichi Yoshida

 

 

 

 

Tuesday, October 11, 2016

 

7:30 

- 8:45

Continental Breakfast - Prefunction (outside Garden State)

 

 

Session 3.1a - Regency BC

Session 3.1b - Garden State ABC

9:00 

- 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:25 

- 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

9:50 

- 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:15 

- 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:35 

- 10:55

Coffee Break - Prefunction (outside Garden State)

 

 

Session 3.2a - Regency BC

Session 3.2b - Garden State ABC

10:55 

- 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:20 

- 11:40

Local Conflict Coloring

Agnostic Estimation of Mean and Covariance

 

 

Pierre Fraigniaud, Marc Heinrich, Adrian Kosowski

Kevin Lai, Anup Rao, Santosh Vempala

11:45 

- 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:10 

- 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

12:30 

- 2:30

Lunch - Brunswick

 

 

Session 3.3a - Regency BC

Session 3.3b - Garden State ABC

2:30 

- 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

2:55 

- 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:20 

- 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

3:45 

- 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:05 

- 4:25

Coffee Break - Prefunction (outside Garden State)

 

 

Session 3.4a - Regency BC

Session 3.4b - Garden State ABC

4:25 

- 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

4:50 

- 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:15 

- 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