Sponsor and location: Simons Institute (directions).
      For preliminary proceedings, click here. (Username is itcs and password is the year of the conference.)

Monday, January 9th, 2017

08:50-10:10    Session 1 Chair: Christos Papadimitriou
08:50-09:10 James Lee Separators in region intersection graphs (invited paper) [video]
09:10-09:20 Ioannis Panageas and Georgios Piliouras Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions [video]
09:20-09:30 Zeyuan Allen-Zhu and Lorenzo Orecchia Linear Coupling of Gradient and Mirror Descent [video]
09:30-09:40 David Mass and Tali Kaufman High Dimensional Random Walks and Colorful Expansion [video]
09:40-10:00 Prasad Raghavendra, Nicholas Ryder and Nikhil Srivastava Real-Stability Testing [video]
10:40-12:00    Session 2 Chair: Alessandro Chiesa [video]
10:40-11:00 Silvio Micali Fast and Furious Byzantine Agreement [video]
11:00-11:10 Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz and Vinod Vaikuntanathan Low-Complexity Cryptographic Hash Functions [video]
11:10-11:20 Zvika Brakerski, Nishanth Chandran, Vipul Goyal, Aayush Jain, Amit Sahai and Gil Segev Hierarchical Functional Encryption [video]
11:20-11:40 Arpita Ghosh and Robert Kleinberg Inferential Privacy Guarantees for Differentially Private Mechanisms [video]
11:40-11:50 Jeremiah Blocki, Manuel Blum, Anupam Datta and Santosh Vempala Towards Human Computable Passwords [video]
12:00-13:30 Lunch (on your own)
13:30-14:40    Session 3 Chair: Aviad Rubinstein [video]
13:30-13:40 Amir Abboud and Arturs Backurs Towards Hardness of Approximation for Polynomial Time Problems [video]
13:40-13:50 Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova and Nithin Varma Parameterized Property Testing of Functions [video]
13:50-14:10 Shafi Goldwasser and Dhiraj Holden The Complexity of Problems in P Given Correlated Instances [video]
14:10-14:20 Martin Fürer Multi-Clique-Width [video]
15:00-16:10    Session 4 Chair: Georgios Piliouras [video]
15:00-15:10 Nancy Lynch, Cameron Musco and Merav Parter Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks [video]
15:10-15:20 Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali and Vijay Vazirani Mutation, Sexual Reproduction and Survival in Dynamic Environments [video]
15:20-15:30 Bernard Chazelle and Chu Wang Self-Sustaining Iterated Learning [video]
15:30-15:50 Damian Straszak and Nisheeth Vishnoi IRLS and Slime Mold (invited paper) [video]
16:00-17:30 Reception and Poster Session
18:00-20:00 Graduating Bits

Tuesday, January 10th, 2017

08:50-10:10    Session 5 Chair: Mary Wootters [video]
08:50-09:10 Mark Braverman, Sumegha Garg and Ariel Schvartzman Network coding in undirected graphs is either very helpful or not helpful at all (invited paper) [video]
09:10-09:20 Badih Ghazi, Elad Haramaty, Pritish Kamath and Madhu Sudan Compression in a Distributed Setting [video]
09:20-09:40 Sivakanth Gopi, Zeev Dvir and Jop Briet Outlaw distributions and locally decodable codes [video]
09:40-10:00 Ran Gelles and Yael Kalai Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks [video]
10:40-12:00    Session 6 Chair: Umesh Vazirani [video]
10:40-11:00 Mohammad Bavarian, Thomas Vidick and Henry Yuen Parallel repetition via fortification: analytic view and the quantum case [video]
11:00-11:20 Scott Aaronson, Daniel Grier and Luke Schaeffer The Classification of Reversible Bit Operations [video]
11:20-11:30 Harry Buhrman, Matthias Christandl and Jeroen Zuiddam Nondeterministic quantum communication complexity: the cyclic equality game and iterated matrix multiplication [video]
11:30-11:50 Matthew Hastings Quantum Codes from High-Dimensional Manifolds [video]
12:00-14:00 Lunch (on your own)
14:00-15:30    Session 7 Chair: Aviad Rubinstein [video]
14:00-14:10 Monika Henzinger, Andrea Lincoln, Stefan Neumann and Virginia Vassilevska Williams Conditional Hardness for Sensitivity Problems [video]
14:10-14:30 Benjamin Rossman An Improved Homomorphism Preservation Theorem from Lower Bounds in Circuit Complexity [video]
14:30-14:40 Shalev Ben-David, Pooya Hatami and Avishay Tal Low-Sensitivity Functions from Unambiguous Certificates [video]
14:40-15:00 Clément Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar and Karl Wimmer Testing k-Monotonicity [video]
15:00-15:20 Rocco Servedio and Li-Yang Tan What circuit classes can be learned with non-trivial savings? [video]
15:20-15:40 Sam Buss, Valentine Kabanets, Antonina Kolokolova and Michal Koucky Expander Construction in VNC^1 [video]
16:10-17:40    Session 8 Chair: Robert Kleinberg
16:10-16:30 Steffen Schuldenzucker, Sven Seuken and Stefano Battiston Finding Clearing Payments in Financial Networks with Credit Default Swaps is PPAD-hard [video]
16:30-16:40 Abhinav Bommireddi and Eric Blais Testing submodularity and other properties of valuation functions [video]
16:40-17:00 Yakov Babichenko and Siddharth Barman Algorithmic Aspects of Private Bayesian Persuasion [video]
17:00-17:10 Jon Schneider, Ariel Schvartzman and S. Matthew Weinberg Condorcet-Consistent and Approximately Strategyproof Tournament Rules [video]
17:10-17:30 Nima Anari, Shayan Oveis Gharan, Amin Saberi and Mohit Singh Nash Social Welfare, Matrix Permanent, and Stable Polynomials (invited paper) [video]

Wednesday, January 11th, 2017

08:50-10:10    Session 9 Chair: Alessandro Chiesa [video]
08:50-09:10 Irit Dinur, Prahladh Harsha, Rakesh Venkat and Henry Yuen Multiplayer parallel repetition for expander games (invited paper) [video]
09:10-09:30 Joël Alwen, Susanna F. de Rezende, Jakob Nordström and Marc Vinyals Cumulative Space in Black-White Pebbling and Resolution [video]
09:30-09:40 Tom Gur and Ron Rothblum A Hierarchy Theorem for Interactive Proofs of Proximity [video]
09:40-10:00 Amey Bhangale, Irit Dinur and Inbal Rachel Livni Navon Cube vs Cube Low Degree Test [video]
10:40-12:00    Session 10 Chair: Umesh Vazirani [video]
10:40-10:50 Vitaly Feldman and Badih Ghazi On the Power of Learning from k-Wise Queries [video]
10:50-11:10 Aviad Rubinstein Detecting communities is hard... and counting them is even harder! [video]
11:10-11:30 Jon Kleinberg, Sendhil Mullainathan and Manish Raghavan Inherent Trade-Offs in the Fair Determination of Risk Scores [video]
11:30-11:40 Lennart Gulikers, Marc Lelarge and Laurent Massoulié Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models [video]
11:40-11:50 Brendan Juba Conditional Sparse Linear Regression [video]
12:00-14:00 Lunch (on your own)
14:00-15:20    Session 11 Chair: Henry Yuen [video]
14:00-14:20 Itai Arad, Zeph Landau, Umesh Vazirani and Thomas Vidick Rigorous RG algorithms and area laws for low energy eigenstates in 1D [video]
14:20-14:40 Mathieu Laurière and Dave Touchette The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting [video]
14:40-14:50 Rui Chao, Ben Reichardt, Chris Sutherland and Thomas Vidick Overlapping qubits [video]
14:50-15:10 Iordanis Kerenidis and Anupam Prakash Quantum Recommendation Systems [video]
15:20-16:30    Session 12 Chair: Nikhil Srivastava [video]
15:20-15:30 Yuval Peres, Mohit Singh and Nisheeth Vishnoi Random Walks in Polytopes and Negative Dependence [video]
15:30-15:40 Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat and Clifford Stein Simultaneously Load Balancing for Every p-norm, With Reassignments [video]
15:40-15:50 Michael Dinitz and Zeyu Zhang Approximating Approximate Distance Oracles [video]
15:50-16:00 Christopher Kennedy and Rachel Ward Fast Cross-Polytope Locality-Sensitive Hashing [video]
16:00-16:10 Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi and Erisa Terolli The Distortion of Locality Sensitive Hashing [video]
16:10-16:20 Gabor Ivanyos, Youming Qiao and K. V. Subrahmanyam Constructive non-commutative rank computation is in deterministic polynomial time [video]
16:40-18:00    Session 13 Chair: Christos Papadimitriou [video]
16:40-16:50 Leonard J. Schulman and Umesh Vazirani The Duality Gap for Two-Team Zero-Sum Games [video]
16:50-17:00 Xi Chen, Yu Cheng and Bo Tang Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games [video]
17:00-17:10 Daniel Stubbs and Virginia Vassilevska Williams Metatheorems for dynamic weighted matching [video]
17:10-17:30 Ryan O'Donnell SOS is not obviously automatizable, even approximately [video]
17:30-17:50 Pavel Hubacek, Moni Naor and Eylon Yogev The Journey from NP to TFNP Hardness (invited paper) [video]