FOCS 2019 Program
Saturday, November 9, 2019
	Constellation D		Constellation E		Constellation F
8:30 - 10:00	Workshop: Beyond worst case analysis of algorithms		Workshop: A TCS Quiver		Tutorial: High-dimensional Expanders
10:00 - 10:15	Coffee Break
10:15 - 11:45	Workshop: Beyond worst case analysis of algorithms		Workshop: A TCS Quiver		Workshop: TCS Early Career Mentoring
11:45 - 1:00	Lunch (on your own)
1:00 - 2:30	Tutorial: Theoretical Foundations of Active Learning		Workshop: A TCS Quiver		Workshop: TCS Early Career Mentoring
2:30 - 3:00	Coffee Break
	Constellation DEF
3:00 - 6:00	ShafiFest
6:00 - 8:00	Welcome Reception
Sunday, November 10, 2019
7:30 - 8:30	Breakfast (Atrium)
	Session 1A (Constellation CD)			Session 1B (Constellation EF)
8:30 - 8:50	Tight Bounds for Online Edge Coloring			How to Use Heuristics for Differential Privacy
	Ilan Reuven Cohen, Binghui Peng, David Wajc			Seth Neel, Aaron Roth, Zhiwei Steven Wu
8:55 - 9:15	Online Matching with General Arrivals			The Role of Interactivity in Local Differential Privacy
	Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, David Wajc			Matthew Joseph, Jieming Mao, Seth Neel, Aaron Roth
9:20 - 9:40	Polylogarithmic Guarantees for Generalized Reordering Buffer Management			Learning from Outcomes: Evidence-Consistent Rankings
	Matthias Englert, Harald Räcke, Richard Stotz			Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona
9:45 - 10:05	General Framework for Metric Optimization Problems with Delay or with Deadlines			Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits
	Yossi Azar, Noam Touitou			Chao Tao, Qin Zhang, Yuan Zhou
10:05	Coffee Break
	Session 2A (Constellation CD)			Session 2B (Constellation EF)
10:25 - 10:45	Derandomization from Algebraic Hardness: Treading the Borders			Adversarial Bandits with Knapsacks
	Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon			Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, Aleksandrs Slivkins
10:50 - 11:10	Expander Graphs -- Both local and global			Approximation Schemes for a Buyer with Independent Items via Symmetries
	Michael Chapman, Nati Linial, Yuval Peled			Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman, Sahil Singla, S. Matthew Weinberg
11:15 - 11:35	Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error			Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
	Benny Applebaum, Eliran Kachlon			Sepehr Assadi, Sahil Singla
11:40 - 12:00	Approximating Constraint Satisfaction Problems on High-Dimensional Expanders			Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers
	Vedat Levi Alev, Fernando Granha Jeronimo, Madhur Tulsiani			Tomer Ezra, Michal Feldman, Eric Neyman, Inbal Talgam-Cohen, S. Matthew Weinberg
12:00	Lunch (on your own)
	Session 3A (Constellation CD)			Session 3B (Constellation EF)
1:45 - 2:05	Reed-Muller codes polarize			Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time
	Emmanuel Abbe, Min Ye			Shiri Chechik, Tianyi Zhang
				Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
				Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan
2:10 - 2:30	SETH-hardness of Coding Problems			A New Deterministic Algorithm for Dynamic Set Cover
	Noah Stephens-Davidowitz, Vinod Vaikuntanathan			Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
2:35 - 2:55	Quasilinear time list-decodable codes for space bounded channels			Sensitive Distance and Reachability Oracles for Large Batch Updates
	Swastik Kopparty, Ronen Shaltiel, Jad Silbak			Jan van den Brand, Thatchaphol Saranurak
3:00 - 3:20	An Optimal Document Exchange Protocol			Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time
	Bernhard Haeupler			Jan van den Brand, Danupon Nanongkai
3:25 - 3:45	Radio Network Coding Requires Logarithmic Overhead			Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds
	Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena			Jan van den Brand, Danupon Nanongkai, Thatchaphol Saranurak
3:45	Coffee Break
	Session 4 (Constellation CDEF)
4:05 - 4:25	Lower bounds for maximal matchings and maximal independent sets
	Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
4:30 - 4:50	Automating Resolution is NP-Hard
	Albert Atserias, Moritz Müller
4:55 - 5:15	NEEXP is contained in MIP*
	Anand Natarajan, John Wright
	Break
5:30	60th FOCS Celebration (Constellation CDEF, dinner in Atrium at 6:30)
8:00	Business Meeting (Constellation CDEF)
Monday, November 11, 2019
7:30 - 8:30	Breakfast (Atrium)
	Session 5A (Constellation CD)			Session 5B (Constellation EF)
8:30 - 8:50	Inapproximability of Clustering in Lp-metrics			Perfect zero knowledge for quantum multiprover interactive proofs
	Vincent Cohen-Addad, Karthik C. S.			Alex B. Grilo, William Slofstra, Henry Yuen
8:55 - 9:15	Near-Linear-Time Approximation Schemes for Clustering in Doubling Metrics			Leakage-Resilient Secret Sharing Against Colluding Parties
	Vincent Cohen-Addad, Andreas Emil Feldmann, David Saulpic			Ashutosh Kumar, Raghu Meka, Amit Sahai
9:20 - 9:40	A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs			Laconic Conditional Disclosure of Secrets and Applications
	Vincent Cohen-Addad, Marcin Pilipczuk, Michał Pilipczuk			Nico Döttling, Sanjam Garg, Vipul Goyal, Giulio Malavolta
9:45 - 10:05	Smoothed Analysis in Unsupervised Learning via Decoupling			Non-Malleable Commitments using Goldreich-Levin List Decoding
	Aditya Bhaskara, Aidao Chen, Aidan Perreault, Aravindan Vijayaraghavan			Vipul Goyal, Silas Richelson
10:05	Coffee Break
	Session 6A (Constellation CD)			Session 6B (Constellation EF)
10:25 - 10:45	Distributed local approximation algorithms for maximum matching in graphs and hypergraphs			Fast generalized DFTs for all finite groups
	David G. Harris			Chris Umans
10:50 - 11:10	Beyond the Lovasz Local Lemma: Point to Set Correlations and Their Algorithmic Applications			Waring Rank, Parameterized and Exact Algorithms
	Dimitris Achlioptas, Fotis Iliopoulos, Alistair Sinclair			Kevin Pratt
11:15 - 11:35	Beyond trace reconstruction: Population recovery from the deletion channel			More barriers for rank methods, via a "numeric to symbolic" transfer
	Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha			Ankit Garg, Visu Makam, Rafael Oliveira, Avi Wigderson
11:40 - 12:00	Multi-Resolution Hashing for Fast Pairwise Summations			Towards a theory of non-commutative optimization: geodesic 1st and 2nd order methods for moment maps and polytopes
	Moses Charikar, Paris Siminelakis			Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Oliveira, Michael Walter, Avi Wigderson
12:00	Lunch (on your own)
	Session 7A (Constellation CD)			Session 7B (Constellation EF)
1:45 - 2:05	Planar Graphs have Bounded Queue-Number			A Quantum Query Complexity Trichotomy for Regular Languages
	Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood			Scott Aaronson, Daniel Grier, Luke Schaeffer
2:10 - 2:30	Parametric Shortest Paths in Planar Graphs			Exponential Separation between Quantum Communication and Logarithm of Approximate Rank
	Kshitij Gajjar, Jaikumar Radhakrishnan			Makrand Sinha, Ronald de Wolf
				Quantum Log-Approximate-Rank Conjecture is also False
				Anurag Anshu, Naresh Goud Boddu, Dave Touchette
2:35 - 2:55	Random k-out subgraph leaves only O(n/k) inter-component edges			Quantum advantage with noisy shallow circuits in 3D
	Jacob Holm, Valerie King, Mikkel Thorup, Or Zamir, Uri Zwick			Sergey Bravyi, David Gosset, Robert Koenig, Marco Tomamichel
3:00 - 3:20	New Notions and Constructions of Sparsification for Graphs and Hypergraphs			Stoquastic PCP vs. Randomness
	Nikhil Bansal, Ola Svensson, Luca Trevisan			Dorit Aharonov, Alex B. Grilo
3:25 - 3:45	Linear-Time and Efficient Distributed Algorithms for List Coloring Graphs on Surfaces			Computationally-secure and composable remote state preparation
	Luke Postle			Alexandru Gheorghiu, Thomas Vidick
3:45 - 4:45	Job Market Posters and Coffee Break (Atrium)
	Session 8 (Constellation CDEF)
4:45 - 5:05	Efficient Construction of Rigid Matrices Using an NP Oracle
	Josh Alman, Lijie Chen
5:10 - 5:30	Faster Minimum k-cut of a Simple Graph
	Jason Li
5:35 - 5:55	Truly Optimal Euclidean Spanners
	Hung Le, Shay Solomon
Tuesday, November 12, 2019
7:30 - 8:30	Breakfast (Atrium)
	Session 9A (Constellation CD)			Session 9B (Constellation EF)
8:30 - 8:50	Sublinear Algorithms for Gap Edit Distance			Spectral analysis of matrix scaling and operator scaling
	Elazar Goldenberg, Robert Krauthgamer, Barna Saha			Tsz Chiu Kwok, Lap Chi Lau, Akshay Ramachandran
8:55 - 9:15	Approximation Algorithms for LCS and LIS with Truly Improved Running Times			Noise Sensitivity on the p-Biased Hypercube
	Aviad Rubinstein, Saeed Seddighin, Zhao Song, Xiaorui Sun			Noam Lifshitz, Dor Minzer
9:20 - 9:40	Faster Matroid Intersection			The complexity of 3-colouring H-colourable graphs
	Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, Sam Chiu-wai Wong			Andrei Krokhin, Jakub Opršal
9:45 - 10:05	Balancing Straight-Line Programs			Hardness Magnification for all Sparse NP Languages
	Moses Ganardi, Artur Jez, Markus Lohrey			Lijie Chen, Ce Jin, Ryan Williams
10:05	Coffee Break
	Session 10A (Constellation CD)			Session 10B (Constellation EF)
10:25 - 10:45	The Average-Case Complexity of Counting Cliques in Erdos-Renyi Hypergraphs			Faster polytope rounding, sampling, and volume computation via a sublinear "Ball Walk"
	Enric Boix-Adserà, Matthew Brennan, Guy Bresler			Oren Mangoubi, Nisheeth K. Vishnoi
10:50 - 11:10	Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits			Modified log-Sobolev inequalities for strongly log-concave distributions
	Lijie Chen			Mary Cryan, Heng Guo, Giorgos Mousa
11:15 - 11:35	Why are Proof Complexity Lower Bounds Hard?			Fast uniform generation of random graphs with given degree sequences
	Jan Pich, Rahul Santhanam			Andrii Arman, Pu Gao, Nick Wormald
11:40 - 12:00	Polynomial calculus space and resolution width			A Deterministic Algorithm for Counting Colorings with 2Δ Colors
	Nicola Galesi, Leszek A. Kolodziejczyk, Neil Thapen			Jingcheng Liu, Alistair Sinclair, Piyush Srivastava
12:00	Lunch (on your own)
	Session 11A (Constellation CD)			Session 11B (Constellation EF)
1:45 - 2:05	Breaking of 1RSB in random MAX-NAE-SAT			Finding monotone patterns in sublinear time
	Zsolt Bartha, Nike Sun, Yumeng Zhang			Omri Ben-Eliezer, Clement L. Canonne, Shoham Letzter, Erik Waingarten
2:10 - 2:30	Optimization of the Sherrington-Kirkpatrick Hamiltonian			Agreement testing theorems on layered set systems
	Andrea Montanari			Yotam Dikstein, Irit Dinur
2:35 - 2:55	A Tight Analysis of Bethe Approximation for Permanent			A characterization of graph properties testable for general planar graphs with one-sided error (It's all about forbidden subgraphs)
	Nima Anari, Alireza Rezaei			Artur Czumaj, Christian Sohler
3:00 - 3:20	The Kikuchi Hierarchy and Tensor PCA			Junta-correlation is testable
	Alexander S. Wein, Ahmed El Alaoui, Cristopher Moore			Anindya De, Elchanan Mossel, Joe Neeman
3:20	Coffee Break
	Session 12A (Constellation CD)			Session 12B (Constellation EF)
3:40 - 4:00	An Improved Lower Bound for Sparse Reconstruction from Subsampled Hadamard Matrices			Near-Optimal Massively Parallel Graph Connectivity
	Jaroslaw Blasiok, Patrick Lopatto, Kyle Luh, Jake Marcinek, Shravas Rao			Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, Vahab Mirrokni
4:05 - 4:25	(Nearly) Sample Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless			Exponentially Faster Massively Parallel Maximal Matching
	Vasileios Nakos, Zhao Song, Zhengyu Wang			Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris
4:30 - 4:50	Efficient Truncated Statistics with Unknown Truncation			Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds
	Vasilis Kontonis, Christos Tzamos, Manolis Zampetakis			Mohsen Ghaffari, Fabian Kuhn, Jara Uitto
4:55 - 5:15	Residual Based Sampling for Online Low Rank Approximation			Parallel Reachability in Almost Linear Work and Square Root Depth
	Aditya Bhaskara, Silvio Lattanzi, Sergei Vassilvitskii, Morteza Zadimoghaddam			Yang Liu, Aaron Sidford, Arun Jambulapati