FOCS 2019 Program
Saturday, November 9, 2019
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
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
3:00 - 6:00 ShafiFest
6:00 - 8:00 Welcome Reception
Sunday, November 10, 2019
  Session 1A Session 1B
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 Session 2B
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
  Session 3A Session 3B
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
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 \subseteq MIP*
  Anand Natarajan, John Wright 
5:30 60th FOCS Celebration
8:00 Business Meeting
Monday, November 11, 2019
  Session 5A Session 5B
8:30 - 8:50 Inapproximability of Clustering in l_p-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 Session 6B
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
  Session 7A Session 7B
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
  Session 8
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
  Session 9A Session 9B
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 Session 10B
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
  Session 11A Session 11B
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 Session 12B
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