FOCS 2016 Program

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