FOCS 2019

2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)

Table of Contents

Front MatterPage Number


Session 1A

Tight Bounds for Online Edge Coloring1

Ilan Reuven Cohen (CWI), Binghui Peng (Columbia University), David Wajc (CMU)

Online Matching with General Arrivals26

Buddhima Gamlath (EPFL), Michael Kapralov (EPFL), Andreas Maggiori (EPFL), Ola Svensson (EPFL), David Wajc (CMU)

Polylogarithmic Guarantees for Generalized Reordering Buffer Management38

Matthias Englert (University of Warwick), Harald Räcke (Technical University of Munich), Richard Stotz (Technical University of Munich)

General Framework for Metric Optimization Problems with Delay or with Deadlines60

Yossi Azar (Tel Aviv University), Noam Touitou (Tel Aviv University)


Session 1B

How to Use Heuristics for Differential Privacy72

Seth Neel (University of Pennsylvania), Aaron Roth (University of Pennsylvania), Zhiwei Steven Wu (University of Minnesota)

The Role of Interactivity in Local Differential Privacy94

Matthew Joseph (University of Pennsylvania), Jieming Mao (Google Research New York), Seth Neel (University of Pennsylvania), Aaron Roth (University of Pennsylvania)

Learning from Outcomes: Evidence-Based Rankings106

Cynthia Dwork (Harvard University), Michael P. Kim (Stanford University), Omer Reingold (Stanford University), Guy N. Rothblum (Weizmann Institute of Science), Gal Yona (Weizmann Institute of Science)

Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-armed Bandits126

Chao Tao (Indiana University), Qin Zhang (Indiana University), Yuan Zhou (Indiana University and University of Illinois at Urbana-Champaign)


Session 2A

Derandomization from Algebraic Hardness: Treading the Borders147

Zeyu Guo (IIT Kanpur), Mrinal Kumar (IIT Bombay), Ramprasad Saptharishi (TIFR, Mumbai), Noam Solomon (MIT)

Expander Graphs – Both Local and Global158

Michael Chapman (The Hebrew University of Jerusalem, Israel), Nati Linial (The Hebrew University of Jerusalem, Israel), Yuval Peled (Courant Institute of Mathematical Sciences, NYU, USA)

Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error171

Benny Applebaum (Tel Aviv University, Israel), Eliran Kachlon (Tel Aviv University, Israel)

Approximating Constraint Satisfaction Problems on High-Dimensional Expanders180

Vedat Levi Alev (University of Waterloo, Canada), Fernando Granha Jeronimo (University of Chicago, USA), Madhur Tulsiani (Toyota Technological Institute Chicago, USA)


Session 2B

Adversarial Bandits with Knapsacks202

Nicole Immorlica (Microsoft Research), Karthik Abinav Sankararaman (Facebook/University of Maryland College Park), Robert Schapire (Microsoft Research), Aleksandrs Slivkins (Microsoft Research)

Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries220

Pravesh Kothari (Carnegie Mellon University), Sahil Singla (Princeton University), Divyarthi Mohan (Princeton University), Ariel Schvartzman (Princeton University), S. Matthew Weinberg (Princeton University)

Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders233

Sepehr Assadi (Rutgers University), Sahil Singla (Princeton University and Institute for Advanced Study)

Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers249

Tomer Ezra (Tel Aviv University), Michal Feldman (Tel Aviv University), Eric Neyman (Columbia University), Inbal Talgam-Cohen (Technion), Matt Weinberg (Princeton University)


Session 3A

Reed-Muller Codes Polarize273

Emmanuel Abbe (EPFL (Switzerland) and Princeton University (United States)), Min Ye (Princeton University, United States)

SETH-Hardness of Coding Problems287

Noah Stephens-Davidowitz (Massachussetts Institute of Technology), Vinod Vaikuntanathan (Massachussetts Institute of Technology)

Quasilinear Time List-Decodable Codes for Space Bounded Channels302

Jad Silbak (Tel Aviv University), Swastik Kopparty (Rutgers University), Ronen Shaltiel (University of Haifa)

Optimal Document Exchange and New Codes for Insertions and Deletions334

Bernhard Haeupler (Carnegie Mellon University)

Radio Network Coding Requires Logarithmic Overhead348

Klim Efremenko (Ben-Gurion University), Gillat Kol (Princeton University), Raghuvansh Saxena (Princeton University)


Session 3B

Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time370

Shiri Chechik (Tel Aviv University), Tianyi Zhang (Tsinghua University)

Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time382

Soheil Behnezhad (University of Maryland), Mahsa Derakhshan (University of Maryland), MohammadTaghi Hajiaghayi (University of Maryland), Cliff Stein (Columbia University), Madhu Sudan (Harvard University)

A New Deterministic Algorithm for Dynamic Set Cover406

Sayan Bhattacharya (University of Warwick), Monika Henzinger (University of Vienna), Danupon Nanongkai (KTH Royal Institute of Technology)

Sensitive Distance and Reachability Oracles for Large Batch Updates424

Jan van den Brand (KTH Royal Institute of Technology), Thatchaphol Saranurak (Toyota Technological Institute at Chicago)

Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time436

Jan van den Brand (KTH Royal Institute of Technology), Danupon Nanongkai (KTH Royal Institute of Technology)

Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds456

Jan van den Brand (KTH Royal Institute of Technology), Danupon Nanongkai (KTH Royal Institute of Technology), Thatchaphol Saranurak (Toyota Technological Institute at Chicago)


Session 4

Lower Bounds for Maximal Matchings and Maximal Independent Sets481

Alkida Balliu (Aalto University), Sebastian Brandt (ETH Zurich), Juho Hirvonen (Aalto University), Dennis Olivetti (Aalto University), Mikaël Rabie (Aalto University and LIP6 - Sorbonne Université), Jukka Suomela (Aalto University)

Automating Resolution is NP-Hard498

Albert Atserias (Universitat Politecnica de Catalunya), Moritz Müller (Universitat Politecnica de Catalunya)

NEEXP is Contained in MIP*510

Anand Natarajan (California Institute of Technology), John Wright (California Institute of Technology)


Session 5A

Inapproximability of Clustering in Lp Metrics519

Vincent Cohen-Addad (Sorbonne University), Karthik C. S. (Tel Aviv University)

Near-Linear Time Approximations Schemes for Clustering in Doubling Metrics540

David Saulpic (Sorbonne Université, CNRS, LIP6 and ENS Paris), Vincent Cohen-Addad (Sorbonne Université, CNRS, LIP6), Andreas Feldmann (Charles University in Prague)

A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs560

Vincent Cohen-Addad (Sorbonne Université, CNRS, Laboratoire d’informatique de Paris 6, LIP6), Michał Pilipczuk (University of Warsaw), Marcin Pilipczuk (University of Warsaw)

Smoothed Analysis in Unsupervised Learning via Decoupling582

Aditya Bhaskara (University of Utah), Aidao Chen (Northwestern University), Aidan Perreault (Northwestern University), Aravindan Vijayaraghavan (Northwestern University)


Session 5B

Perfect Zero Knowledge for Quantum Multiprover Interactive Proofs611

Alex Bredariol Grilo (CWI and QuSoft), William Slofstra (University of Waterloo), Henry Yuen (University of Toronto)

Leakage-Resilient Secret Sharing Against Colluding Parties636

Ashutosh Kumar (UCLA), Raghu Meka (UCLA), Amit Sahai (UCLA)

Laconic Conditional Disclosure of Secrets and Applications661

Nico Döttling (CISPA Helmholtz Center for Information Security, Germany), Sanjam Garg (University of California, Berkeley), Vipul Goyal (Carnegie Mellon University), Giulio Malavolta (Simons Institute for the Theory of Computing, USA)

Non-Malleable Commitments using Goldreich-Levin List Decoding686

Vipul Goyal (Carnegie Mellon University), Silas Richelson (UC Riverside)


Session 6A

Beyond the Lovász Local Lemma: Point to Set Correlations and Their Algorithmic Applications725

Dimitris Achlioptas (University of California Santa Cruz), Fotis Iliopoulos (University of California Berkeley), Alistair Sinclair (University of California Berkeley)

Beyond Trace Reconstruction: Population Recovery from the Deletion Channel745

Frank Ban (UC Berkeley), Xi Chen (Columbia University), Adam Freilich (Columbia University), Rocco A. Servedio (Columbia University), Sandip Sinha (Columbia University)

Multi-resolution Hashing for Fast Pairwise Summations769

Moses Charikar (Stanford University), Paris Siminelakis (Stanford University)


Session 6B

Fast Generalized DFTs for all Finite Groups793

Chris Umans (California Institute of Technology)

Waring Rank, Parameterized and Exact Algorithms806

Kevin Pratt (Carnegie Mellon University)

More Barriers for Rank Methods, via a "numeric to Symbolic" Transfer824

Ankit Garg (Microsoft Research India), Visu Makam (Institute for Advanced Study), Rafael Oliveira (University of Toronto), Avi Wigderson (Institute for Advanced Study)

Towards a Theory of Non-Commutative Optimization: Geodesic 1st and 2nd Order Methods for Moment Maps and Polytopes845

Peter Bürgisser (Technische Universität Berlin), Cole Franks (Rutgers University, New Brunswick), Ankit Garg (Microsoft Research India), Rafael Oliveira (University of Toronto), Michael Walter (University of Amsterdam), Avi Wigderson (Institute for Advanced Study)


Session 7A

Planar Graphs have Bounded Queue-Number862

Vida Dujmović (University of Ottawa), Gwenaël Joret (Université libre de Bruxelles), Piotr Micek (Jagiellonian University), Pat Morin (Carleton University), Torsten Ueckerdt (Karlsruhe Institute of Technology), David Wood (Monash University)

Parametric Shortest Paths in Planar Graphs876

Kshitij Gajjar (Tata Institute of Fundamental Research, India), Jaikumar Radhakrishnan (Tata Institute of Fundamental Research, India)

Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges896

Jacob Holm (University of Copenhagen), Valerie King (University of Victoria), Mikkel Thorup (University of Copenhagen), Or Zamir (Tel Aviv University), Uri Zwick (Tel Aviv University)

New Notions and Constructions of Sparsification for Graphs and Hypergraphs910

Nikhil Bansal (CWI and TU Eindhoven), Ola Svensson (EPFL), Luca Trevisan (Bocconi University)


Session 7B

A Quantum Query Complexity Trichotomy for Regular Languages942

Scott Aaronson (UT Austin), Daniel Grier (MIT), Luke Schaeffer (MIT)

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank966

Makrand Sinha (CWI, The Netherlands), Ronald de Wolf (QuSoft, CWI and University of Amsterdam)

Quantum Log-Approximate-Rank Conjecture is Also False982

Anurag Anshu (University of Waterloo and Perimeter Institute, Canada), Naresh Goud Boddu (National University of Singapore), Dave Touchette (University of Waterloo, Perimeter Institute and Universite de Sherbrooke, Canada)

Quantum Advantage with Noisy Shallow Circuits in 3D995

Sergey Bravyi (IBM T. J. Watson Research Center), David Gosset (Department of Combinatorics and Optimization and Institute for Quantum Computing, University of Waterloo), Robert Koenig (Institute for Advanced Study, Zentrum Mathematik, Technical University of Munich), Marco Tomamichel (Centre for Quantum Software and Information, University of Technology Sydney)

Stoquastic PCP vs. Randomness1000

Dorit Aharonov (The Hebrew University of Jerusalem, Israel), Alex Bredariol Grilo (CWI and QuSoft, The Netherlands)

Computationally-Secure and Composable Remote State Preparation1024

Alexandru Gheorghiu (California Institute of Technology), Thomas Vidick (California Institute of Technology)


Session 8

Faster Minimum k-cut of a Simple Graph1056

Jason Li (Carnegie Mellon University)

Truly Optimal Euclidean Spanners1078

Hung Le (University of Victoria), Shay Solomon (Tel Aviv University)


Session 9A

Sublinear Algorithms for Gap Edit Distance1101

Elazar Goldenberg (The Academic College of Tel Aviv-Yaffo), Robert Krauthgamer (Weizmann Institute of Science), Barna Saha (University of California Berkeley)

Approximation Algorithms for LCS and LIS with Truly Improved Running Times1121

Aviad Rubinstein (Stanford University), Saeed Seddighin (Harvard University), Zhao Song (Simons Institute for the Theory of Computing, USA), Xiaorui Sun (University of Illinois at Chicago)

Faster Matroid Intersection1146

Deeparnab Chakrabarty (Dartmouth College), Yin Tat Lee (University of Washington and Microsoft Research), Aaron Sidford (Stanford University), Sahil Singla (Princeton University and Institute for Advanced Study), Sam Chiu-wai Wong (Microsoft Research)

Balancing Straight-Line Programs1169

Moses Ganardi (Universität Siegen), Artur Jeż (University of Wrocław), Markus Lohrey (Universität Siegen)


Session 9B

Spectral Analysis of Matrix Scaling and Operator Scaling1184

Tsz Chiu Kwok (Shanghai University of Finance and Economics), Lap Chi Lau (University of Waterloo), Akshay Ramachandran (University of Waterloo)

Noise Sensitivity on the p -Biased Hypercube1205

Noam Lifshitz (Einstein Institute of Mathematics, Hebrew University of Jerusalem), Dor Minzer (Institute for Advanced Study, Princeton)

The Complexity of 3-Colouring H-Colourable Graphs1227

Andrei Krokhin (Durham University), Jakub Opršal (Durham University)

Hardness Magnification for all Sparse NP Languages1240

Lijie Chen (MIT), Ce Jin (Tsinghua University), R. Ryan Williams (MIT)


Session 10A

The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs1256

Enric Boix-Adserà (MIT), Matthew Brennan (MIT), Guy Bresler (MIT)

Why are Proof Complexity Lower Bounds Hard?1305

Jan Pich (University of Oxford), Rahul Santhanam (University of Oxford)

Polynomial Calculus Space and Resolution Width1325

Nicola Galesi (Sapienza University Rome), Leszek Kolodziejczyk (University of Warsaw), Neil Thapen (Czech Academy of Sciences)


Session 10B

Faster Polytope Rounding, Sampling, and Volume Computation via a Sub-Linear Ball Walk1338

Oren Mangoubi (Worcester Polytechnic Institute, USA), Nisheeth K. Vishnoi (Yale University)

Modified log-Sobolev Inequalities for Strongly Log-Concave Distributions1358

Mary Cryan (University of Edinburgh), Heng Guo (University of Edinburgh), Giorgos Mousa (University of Edinburgh)

Fast Uniform Generation of Random Graphs with Given Degree Sequences1371

Andrii Arman (Monash University), Pu Gao (University of Waterloo), Nicholas Wormald (Monash University)

A Deterministic Algorithm for Counting Colorings with 2-Delta Colors1380

Jingcheng Liu (University of California, Berkeley), Alistair Sinclair (University of California, Berkeley), Piyush Srivastava (Tata Institute of Fundamental Research, India)


Session 11A

Breaking of 1RSB in Random Regular MAX-NAE-SAT1405

Zsolt Bartha (University of California at Berkeley), Nike Sun (Massachusetts Institute of Technology), Yumeng Zhang (Stanford University)

Optimization of the Sherrington-Kirkpatrick Hamiltonian1417

Andrea Montanari (Stanford University)

A Tight Analysis of Bethe Approximation for Permanent1434

Nima Anari (Stanford University), Alireza Rezaei (University of Washington)

The Kikuchi Hierarchy and Tensor PCA1446

Alexander S. Wein (Courant Institute, New York University, USA), Ahmed El Alaoui (Stanford University), Cristopher Moore (Santa Fe Institute)


Session 11B

Finding Monotone Patterns in Sublinear Time1469

Omri Ben-Eliezer (Tel Aviv University), Clément Canonne (Stanford University), Shoham Letzter (ETH Institute for Theoretical Studies), Erik Waingarten (Columbia University)

Agreement Testing Theorems on Layered Set Systems1495

Yotam Dikstein (Weizmann Institute of Science), Irit Dinur (Weizmann Institute of Science)

Junta Correlation is Testable1549

Anindya De (University of Pennsylvania), Elchanan Mossel (MIT), Joe Neeman (UT Austin)


Session 12A

An Improved Lower Bound for Sparse Reconstruction from Subsampled Hadamard Matrices1564

Jaroslaw Blasiok (Harvard University), Patrick Lopatto (Harvard University), Kyle Luh (Harvard University), Jake Marcinek (Harvard University), Shravas Rao (New York University)

(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless1568

Vasileios Nakos (Harvard University), Zhao Song (Harvard University & UT-Austin), Zhengyu Wang (Harvard University)

Efficient Truncated Statistics with Unknown Truncation1578

Vasilis Kontonis (University of Wisconsin-Madison), Christos Tzamos (University of Wisconsin-Madison), Manolis Zampetakis (MIT)

Residual Based Sampling for Online Low Rank Approximation1596

Aditya Bhaskara (University of Utah), Silvio Lattanzi (Google Research Zurich), Sergei Vassilvitskii (Google Research NYC), Morteza Zadimoghaddam (Google Research Zurich)


Session 12B

Near-Optimal Massively Parallel Graph Connectivity1615

Soheil Behnezhad (University of Maryland), Laxman Dhulipala (Carnegie Mellon University), Hossein Esfandiari (Google Research), Jakub Łącki (Google Research), Vahab Mirrokni (Google Research)

Exponentially Faster Massively Parallel Maximal Matching1637

Soheil Behnezhad (University of Maryland), MohammadTaghi Hajiaghayi (University of Maryland), David G. Harris (University of Maryland)

Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds1650

Mohsen Ghaffari (ETH Zurich), Fabian Kuhn (University of Freiburg), Jara Uitto (Aalto University)

Parallel Reachability in Almost Linear Work and Square Root Depth1664

Yang P. Liu (Stanford University), Arun Jambulapati (Stanford University), Aaron Sidford (Stanford University)