





Compressed Zip File of Program and Proceedings  
Saturday, October 8, 2016 
 
6:30 
 8:30 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 
BoundedCommunication Leakage Resilience via ParityResilient Circuits 



Vipul Goyal, Yuval Ishai, Hemanta K. Maji, Amit Sahai, Alexander Sherstov, Hemanta Maji 
Amit Chakrabarti, Sagar Kale 
9:25 
 9:45 
Indistinguishability Obfuscation from DDHlike Assumptions on ConstantDegree Graded Encodings 



Huijia Lin, Vinod Vaikuntanathan 
Djamal Belazzougui, Qin Zhang 
9:50 
 10:10 
Breaking the Three Round Barrier for NonMalleable Commitments 



Vipul Goyal, Dakshita Khurana, Amit Sahai 
Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup 
10:15 
 10:35 



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 



Johan Hastad 
Andras Sebo, Anke van Zuylen 
11:20 
 11:40 
A Betterthan3n Lower Bound for the Circuit Complexity of an Explicit Function 
Hopsets with Constant Hopbound, and Applications to 


Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov 
Michael Elkin, Ofer Neiman 
11:45 
 12:05 



Shiteng Chen, Periklis A. Papakonstantinou 
Sungjin Im, Shi Li 
12:10 
 12:30 
A Deterministic Polynomial Time Algorithm for Noncommutative 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, TH. 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 



Gil Cohen, Leonard J. Schulman 
Shahar Dobzinski 
2:55 
 3:15 
Making the Most of Advice: New Correlation Breakers and Their Applications 



Gil Cohen 
Constantinos Daskalakis, Vasilis Syrgkanis 
3:20 
 3:40 



Eshan Chattopadhyay, Xin Li 
Tim Roughgarden, Omri Weinstein 
3:45 
 4:05 
Improved TwoSource Extractors, and Affine Extractors for Polylogarithmic Entropy 



Xin Li 
Yiling Chen, Bo Waggoner 
4:10 
 4:30 
The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling 



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 Twoplayer Nash Equilibria 



Aviad Rubinstein 

5:05 
 5:25 
Fast Learning Requires Good Memory: A TimeSpace Lower Bound for Parity Learning 



Ran Raz 

5:30 
 5:50 



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 



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 



Timothy Gowers, Emanuele Viola 
Shay Solomon 
9:50 
 10:10 



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 CellProbe Lower Bounds from FourParty Communication 



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



Vincent CohenAddad, Philip N. Klein, Claire Mathieu 

11:10 
 11:25 



Zachary Friggstad, Mohsen Rezapour, Mohammad Salavatipour 

11:30 
 11:50 



Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams 



Session 2.3  Regency BC 

12:00 
 1:00 



Noam Nisan, Hebrew University of Jerusalem 

1:00 
 2:30 
Lunch  Brunswick 



Session 2.4  Regency BC 

2:30 
 2:50 



Peter Bürgisser, Christian Ikenmeyer, Greta Panova 



Rectangular Kronecker Coefficients and Plethysms in Geometric Complexity Theory 



Christian Ikenmeyer, Greta Panova 

2:55 
 3:15 



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

3:20 
 3:40 
A Discrete and Bounded Envyfree 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 SumofSquares Lower Bound for the Planted Clique Problem 



Boaz Barak, Samuel B.Hopkins, Jonathan Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin 
Arturs Backurs, Piotr Indyk 
4:20 
 4:40 
Polynomial Representations of Threshold Functions with Applications 



Tengyu Ma, Jonathan Shi, David Steurer 
Josh Alman, Timothy M. Chan, Ryan Williams 
4:45 
 5:05 
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 
MaxInformation, Differential Privacy, and PostSelection 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 NodePrivate Graph Statistics and the Generalized Exponential Mechanism 



Sofya Raskhodnikova, Adam Smith 
Fedor V. Fomin, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Micha Pilipczuk, Saket Saurabh 
6:10 
 6:30 





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 
Approximate Gaussian Elimination for Laplacians  Fast, 


Alexander A. Sherstov 
Rasmus Kyng, Sushant Sachdeva 
9:25 
 9:45 
Decidability of NonInteractive 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 



Anurag Anshu, Aleksandrs Belovs, Shalev BenDavid, Mika Göös, Robin Kothari, Rahul Jain, Troy Lee, Miklos Santha 
Aleksander Madry 
10:15 
 10:35 



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 


YiJun Chang, Tsvi Kopelowitz, Seth Pettie 
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart 
11:20 
 11:40 



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 



David Karger 
Anindya De, Michael Saks, Sijian Tang 
12:10 
 12:30 
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 HardCore Model 



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 



Elizabeth Crosson, Aram Harrow 
Venkatesan Guruswami, David Zuckerman 
3:45 
 4:05 
NPHardness of ReedSolomon Decoding and the ProuhetTarryEscott 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 
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 



Vladimir Kolmogorov 
TH. Hubert Chan, Shuguang Hu, Shaofeng H.C. Jiang 
5:15 
 5:35 
Algorithm for Komlós Conjecture: Matching Banaszczyk's Bound 



Nikhil Bansal, Daniel Dadush, Shashwat Garg 
Julia Chuzhoy, Alina Ene 