FOCS 2020

2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)

Table of Contents

Front MatterPage Number


Session 1A

Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization1

Lijie Chen (MIT), Xin Lyu (Tsinghua University), R. Ryan Williams (MIT)

On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds [Extended Abstract]13

Lijie Chen (MIT, USA), Ron D. Rothblum (Technion, Israel), Roei Tell (MIT, USA), Eylon Yogev (Boston University, USA and Tel Aviv University, Israel)

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity24

Susanna de Rezende (Institute of Mathematics of the Czech Academy of Sciences, Czech Republic), Or Meir (University of Haifa, Israel), Jakob Nordstrom (University of Copenhagen and Lund University, Denmark and Sweden), Toniann Pitassi (University of Toronto and IAS, Canada, USA), Robert Robere (McGill University, Canada), Marc Vinyals (Technion, Israel)

Tree-Depth and the Formula Complexity of Subgraph Isomorphism31

Deepanshu Kush (University of Toronto, Canada), Benjamin Rossman (Duke University, USA)

KRW Composition Theorems via Lifting43

Susanna F. de Rezende (Institute of Mathematics of the Czech Academy of Sciences, Czech Republic), Or Meir (University of Haifa, Israel), Jakob Nordström (University of Copenhagen, Denmark, and Lund University, Sweden), Toniann Pitassi (University of Toronto, Canada, and Institute of Advanced Study, USA), Robert Robere (McGill University, Canada)

Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity50

Shuichi Hirahara (National Institute of Informatics, Japan)


Session 1B

Near-Linear Size Hypergraph Cut Sparsifiers61

Yu Chen (University of Pennsylvania, USA), Sanjeev Khanna (University of Pennsylvania, USA), Ansh Nagda (University of Washington, USA)

Towards Better Approximation of Graph Crossing Number73

Julia Chuzhoy (Toyota Technological Institute at Chicago), Sepideh Mahabadi (Toyota Technological Institute at Chicago), Zihan Tan (University of Chicago)

Deterministic Min-cut in Poly-Logarithmic Max-Flows85

Jason Li (CMU), Debmalya Panigrahi (Duke University)

Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs93

Kyriakos Axiotis (MIT), Aleksander Mądry (MIT), Adrian Vladu (Boston University)

Cut-Equivalent Trees are Optimal for Min-Cut Queries105

Amir Abboud (IBM Almaden, USA), Robert Krauthgamer (Weizmann Institute of Science, Israel), Ohad Trabelsi (Weizmann Institute of Science, Israel)

Unit Capacity Maxflow in Almost m^(4/3) Time119

Tarun Kathuria (UC Berkeley), Yang P. Liu (Stanford University), Aaron Sidford (Stanford University)


Session 1C

Low-Degree Hardness of Random Optimization Problems131

David Gamarnik (Massachusetts Institute of Technology, USA), Aukosh Jagannath (University of Waterloo, Canada), Alexander S. Wein (New York University, USA)

List Decodable Mean Estimation in Nearly Linear Time141

Yeshwanth Cherapanamjeri (University of California at Berkeley), Sidhanth Mohanty (University of California at Berkeley), Morris Yau (University of California at Berkeley)

Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures149

Ainesh Bakshi (CMU, USA), Ilias Diakonikolas (UW Madison, USA), Samuel B. Hopkins (UC Berkeley, USA), Daniel Kane (UC San Diego, USA), Sushrut Karmalkar (UT Austin, USA), Pravesh K. Kothari (CMU, USA)

Collaborative Top Distribution Identifications with Limited Interaction (Extended Abstract)160

Nikolai Karpov (Indiana University Bloomington), Qin Zhang (Indiana University Bloomington), Yuan Zhou (University of Illinois at Urbana-Champaign)

Kernel Density Estimation through Density Constrained Near Neighbor Search172

Moses Charikar (Stanford University, USA), Michael Kapralov (EPFL, Switzerland), Navid Nouri (EPFL, Switzerland), Paris Siminelakis (UC Berkeley, USA)

Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models184

Ilias Diakonikolas (UW Madison), Daniel M. Kane (UC San Diego)


Session 2A

QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge196

Anne Broadbent (University of Ottawa), Alex Bredariol Grilo (LIP6, CNRS/Sorbonne Université)

Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise206

Noah Shutty (Stanford University, USA), Mary Wootters (Stanford University, USA), Patrick Hayden (Stanford University, USA)

Decodable Quantum LDPC Codes Beyond the Square Root Distance Barrier using High Dimensional Expanders218

Shai Evra (Institute for Advanced Studies, Princeton), Tali Kaufman (Dept. of Computer Science, Bar-Ilan University, Israel), Gilles Zémor (Institut de Mathématiques de Bordeaux, UMR 5251, Université de Bordeaux, France)

A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions240

Shalev Ben-David (University of Waterloo), Eric Blais (University of Waterloo)

Towards a Proof of the Fourier–Entropy Conjecture?247

Esty Kelman (Tel-Aviv University), Guy Kindler (Hebrew University of Jerusalem), Noam Lifshitz (Hebrew University of Jerusalem), Dor Minzer (Massachusetts Institute of Technology), Muli Safra (Tel-Aviv University)


Session 2B

Mechanisms for a No-Regret Agent: Beyond the Common Prior259

Modibo K. Camara (Northwestern University), Jason D. Hartline (Northwestern University), Aleck Johnsen (Northwestern University)

Smoothed Complexity of 2-Player Nash Equilibria271

Shant Boodaghians (University of Illinois at Urbana-Champaign), Joshua Brakensiek (Stanford University), Samuel B. Hopkins (University of California, Berkeley), Aviad Rubinstein (Stanford University)

Coordinate Methods for Matrix Games283

Yair Carmon (Tel Aviv University, Stanford University), Yujia Jin (Stanford University), Aaron Sidford (Stanford University), Kevin Tian (Stanford University)

Benchmark Design and Prior-Independent Optimization294

Jason Hartline (Northwestern University), Aleck Johnsen (Northwestern University), Yingkai Li (Northwestern University)

An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions306

Paul Dütting (London School of Economics, UK), Thomas Kesselheim (University of Bonn, Germany), Brendan Lucier (Microsoft Research, USA)


Session 2C

The Coin Problem with Applications to Data Streams318

Mark Braverman (Princeton University, USA), Sumegha Garg (Harvard University, USA), David P. Woodruff (CMU, USA)

Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT330

Chi-Ning Chou (Harvard University), Alexander Golovnev (Harvard University), Santhoshini Velusamy (Harvard University)

Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms342

Sepehr Assadi (Rutgers University, USA), Ran Raz (Princeton University, USA)

Multi-pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems354

Sepehr Assadi (Rutgers University), Gillat Kol (Princeton University), Raghuvansh R. Saxena (Princeton University), Huacheng Yu (Princeton University)

Distributed Lower Bounds for Ruling Sets365

Alkida Balliu (University of Freiburg), Sebastian Brandt (ETH Zurich), Dennis Olivetti (University of Freiburg)

Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization377

Yi-Jun Chang (ETH Institute for Theoretical Studies), Thatchaphol Saranurak (Toyota Technological Institute of Chicago)


Session 3: Plenary Session

An Equivalence Between Private Classification and Online Prediction389

Mark Bun (Department of Computer Science University of Bostong), Roi Livni (Department of Electrical Engineering, Tel Aviv University), Shay Moran (Department of Mathematics, Technion)

A New Minimax Theorem for Randomized Algorithms (Extended Abstract)403

Shalev Ben-David (University of Waterloo), Eric Blais (University of Waterloo)

Edge-Weighted Online Bipartite Matching412

Matthew Fahrbach (Google Research), Zhiyi Huang (The University of Hong Kong), Runzhou Tao (Columbia University), Morteza Zadimoghaddam (Google Research)

Constant Depth Formula and Partial Function Versions of MCSP are Hard424

Rahul Ilango (Massachusetts Institute of Technology)


Session 4A

Unique Decoding of Explicit ε-Balanced Codes Near the Gilbert--Varshamov Bound434

Fernando Granha Jeronimo (University of Chicago), Dylan Quintana (University of Chicago), Shashank Srivastava (TTIC), Madhur Tulsiani (TTIC)

Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes446

Zvika Brakerski (Weizmann Institute of Science), Yael Tauman Kalai (Microsoft and MIT), Raghuvansh R. Saxena (Princeton University)

LDPC Codes Achieve List Decoding Capacity458

Jonathan Mosheiff (Canegie Mellon University, USA), Nicolas Resch (Canegie Mellon University, USA), Noga Ron-Zewi (University of Haifa, Israel), Shashwat Silas (Stanford University, USA), Mary Wootters (Stanford University, USA)

Binary Interactive Error Resilience Beyond 1/8 (or why (1/2)^3 > 1/8)470

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

Coded Trace Reconstruction in a Constant Number of Traces482

Joshua Brakensiek (Stanford University, USA), Ray Li (Stanford University, USA), Bruce Spang (Stanford University, USA)

Network Coding Gaps for Completion Times of Multiple Unicasts494

Bernhard Haeupler (Carnegie Mellon University), David Wajc (Stanford), Goran Zuzic (ETH Zurich)


Session 4B

Robust and Sample Optimal Algorithms for PSD Low Rank Approximation506

Ainesh Bakshi (CMU, USA), Nadiia Chepurko (MIT, USA), David P. Woodruff (CMU, USA)

Near Optimal Linear Algebra in the Online and Sliding Window Models517

Vladimir Braverman (Johns Hopkins University), Petros Drineas (Purdue University), Cameron Musco (University of Massachusetts Amherst), Christopher Musco (New York University), Jalaj Upadhyay (Apple, Inc.), David P. Woodruff (Carnegie Mellon University), Samson Zhou (Carnegie Mellon University)

Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time529

Jess Banks (UC Berkeley), Jorge Garza-Vargas (UC Berkeley), Archit Kulkarni (UC Berkeley), Nikhil Srivastava (UC Berkeley)

Algorithms and Hardness for Linear Algebra on Geometric Graphs541

Josh Alman (Harvard University), Timothy Chu (Carnegie Mellon University), Aaron Schild (University of Washington), Zhao Song (Columbia University, Princeton University, and Institute for Advanced Study)

Sparse PCA: Algorithms, Adversarial Perturbations and Certificates553

Tommaso d'Orsi (ETH Zurich), Pravesh K. Kothari (Carnegie-Mellon University), Gleb Novikov (ETH Zurich), David Steurer (ETH Zurich)

Maximizing Determinants Under Matroid Constraints565

Vivek Madan (Amazon), Aleksandar Nikolov (University of Toronto), Mohit Singh (Georgia Institute of Technology), Uthaipon (Tao) Tantipongpipat (Twitter)


Session 4C

Adjacency Labelling for Planar Graphs (and Beyond)577

Vida Dujmović (University of Ottawa, Canada), Louis Esperet (CNRS, Univ. Grenoble Alpes, France), Cyril Gavoille (Université de Bordeaux, France), Gwenaël Joret (Université Libre de Bruxelles, Belgium), Piotr Micek (Jagiellonian University, Poland), Pat Morin (Carleton University, Canada)

On Light Spanners, Low-Treewidth Embeddings and Efficient Traversing in Minor-free Graphs589

Vincent Cohen-Addad (Google Research), Arnold Filtser (Columbia University), Philip N. Klein (Brown University), Hung Le (University of Massachusetts at Amherst)

Twin-Width I: Tractable FO Model Checking601

Édouard Bonnet (ENS Lyon, LIP), Eun Jung Kim (Paris-Dauphine University, LAMSADE), Stéphan Thomassé (ENS Lyon, LIP), Rémi Watrigant (ENS Lyon, LIP)

Independent Set on P_k-Free Graphs in Quasi-Polynomial Time613

Peter Gartland (University of California at Santa Barbara), Daniel Lokshtanov (University of California at Santa Barbara)

Isomorphism Testing for Graphs Excluding Small Minors625

Martin Grohe (RWTH Aachen University), Daniel Neuen (CISPA Helmholtz Center for Information Security), Daniel Wiebking (RWTH Aachen University)


Session 5A

Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving637

Simon Apers (CWI, the Netherlands; Inria, France; ULB, Belgium), Ronald de Wolf (QuSoft, CWI and University of Amsterdam, the Netherlands)

Symmetries, Graph Properties, and Quantum Speedups649

Shalev Ben-David (University of Waterloo, Canada), Andrew M. Childs (University of Maryland, USA), András Gilyén (California Institute of Technology, USA), William Kretschmer (University of Texas at Austin, USA), Supartha Podder (University of Ottawa, Canada), Daochen Wang (University of Maryland, USA)

Quantum Isomorphism is Equivalent to Equality of Homomorphism Counts from Planar Graphs661

Laura Mančinska (University of Copenhagen, Denmark), David E. Roberson (Technical University of Denmark, Denmark)

Tight Quantum Time-Space Tradeoffs for Function Inversion673

Kai-Min Chung (Academia Sinica, Taiwan), Siyao Guo (New York University Shanghai, China), Qipeng Liu (Princeton University & NTT Research, USA), Luowen Qian (Boston University, USA)

Sample-Efficient Learning of Quantum Many-Body Systems685

Anurag Anshu (University of Waterloo and Perimeter Institute, Canada), Srinivasan Arunachalam (IBM Research, USA), Tomotaka Kuwahara (RIKEN Center, Japan), Mehdi Soleimanifar (MIT, USA)

Entanglement is Necessary for Optimal Quantum Property Testing692

Sebastien Bubeck (Microsoft Research, USA), Sitan Chen (MIT, USA), Jerry Li (Microsoft Research, USA)


Session 5B

Lazy Search Trees704

Bryce Sandlund (University of Waterloo), Sebastian Wild (University of Liverpool)

2D Generalization of Fractional Cascading on Axis-Aligned Planar Subdivisions716

Peyman Afshani (Aarhus University), Pingan Cheng (Aarhus University)

Subsets and Supermajorities: Optimal Hashing-Based Set Similarity Search728

Thomas D. Ahle (BARC, IT University of Copenhagen, Denmark), Jakob B. T. Knudsen (BARC, University of Copenhagen, Denmark)

Polynomial Data Structure Lower Bounds in the Group Model740

Alexander Golovnev (Harvard University), Gleb Posobin (Columbia University), Oded Regev (Courant Institute of Mathematical Sciences, New York University), Omri Weinstein (Columbia University)

An Adaptive Step Toward the Multiphase Conjecture752

Young Kun Ko (New York University), Omri Weinstein (Columbia University)


Session 5C

New Techniques for Proving Fine-Grained Average-Case Hardness774

Mina Dalirrooyfard (MIT), Andrea Lincoln (MIT), Virginia Vassilevska Williams (MIT)

Monochromatic Triangles, Triangle Listing and APSP786

Virginia Vassilevska Williams (Massachusetts Institute of Technology, USA), Yinzhan Xu (Massachusetts Institute of Technology, USA)

A Parameterized Approximation Scheme for Min k-Cut798

Daniel Lokshtanov (University of California, Santa Barbara, USA), Saket Saurabh (The Institute of Mathematical Sciences, HBNI, Chennai, India, and University of Bergen, Norway), Vaishali Surianarayanan (University of California, Santa Barbara, USA)

Hypergraph k-cut for Fixed k in Deterministic Polynomial Time810

Karthekeyan Chandrasekaran (University of Illinois, Urbana-Champaign), Chandra Chekuri (University of Illinois, Urbana-Champaign)

Scheduling with Communication Delays via LP Hierarchies and Clustering822

Sami Davies (University of Washington), Janardhan Kulkarni (Microsoft Research), Thomas Rothvoss (University of Washington), Jakub Tarnawski (Microsoft Research), Yihao Zhang (University of Washington)

Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay834

Biswaroop Maiti (Northeastern University, USA), Rajmohan Rajaraman (Northeastern University, USA), David Stalfa (Northeastern University, USA), Zoya Svitkina (Google Research, USA), Aravindan Vijayaraghavan (Northwestern University, USA)


Session 6A

Local Proofs Approaching the Witness Length [Extended Abstract]846

Noga Ron-Zewi (University of Haifa, Israel), Ron D. Rothblum (Technion, Israel)

Rigid Matrices from Rectangular PCPs or: Hard Claims Have Complex Proofs858

Amey Bhangale (University of California, Riverside, USA), Prahladh Harsha (Tata Institute of Fundamental Research, Mumbai, India), Orr Paradise (University of California, Berkeley, USA), Avishay Tal (University of California, Berkeley, USA)

On the Existence of Algebraically Natural Proofs870

Prerona Chatterjee (STCS, TIFR, Mumbai, India), Mrinal Kumar (Dept. of CS&E, IIT Bombay, Mumbai, India), C. Ramya (STCS, TIFR, Mumbai, India), Ramprasad Saptharishi (STCS, TIFR, Mumbai, India), Anamay Tengse (STCS, TIFR, Mumbai, India)

Symbolic Determinant Identity Testing (SDIT) is not a null cone Problem; and the Symmetries of Algebraic Varieties881

Visu Makam (Institute for Advanced Study), Avi Wigderson (Institute for Advanced Study)

Learning sums of Powers of Low-Degree Polynomials in the Non-Degenerate Case889

Ankit Garg (Microsoft Research India), Neeraj Kayal (Microsoft Research India), Chandan Saha (Indian Institute of Science, Bengaluru)

Proximity Gaps for Reed–Solomon Codes900

Eli Ben-Sasson (StarkWare, Israel), Dan Carmon (StarkWare, Israel), Yuval Ishai (Technion, Israel), Swastik Kopparty (Rutgers University, New Jersey), Shubhangi Saraf (Rutgers University, New Jersey)


Session 6B

A Faster Interior Point Method for Semidefinite Programming910

Haotian Jiang (University of Washington), Tarun Kathuria (University of California, Berkeley), Yin Tat Lee (University of Washington, Microsoft Research Redmond), Swati Padmanabhan (University of Washington), Zhao Song (Columbia University, Princeton University, and Institute for Advanced Study)

Bipartite Matching in Nearly-Linear Time on Moderately Dense Graphs919

Jan van den Brand (KTH Royal Institute of Technology, Sweden), Yin-Tat Lee (University of Washington and Microsoft Research Redmond, USA), Danupon Nanongkai (KTH Royal Institute of Technology, Sweden), Richard Peng (Georgia Institute of Technology, USA), Thatchaphol Saranurak (Toyota Technological Institute at Chicago, USA), Aaron Sidford (Stanford University, USA), Zhao Song (Columbia University, Princeton University and Institute for Advanced Study, USA), Di Wang (Google Research, USA)

Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers931

Daniel Dadush (Centrum Wiskunde & Informatica, The Netherlands), Bento Natura (London School of Economics and Political Science, UK), László A. Végh (London School of Economics and Political Science, UK)

Subexponential LPs Approximate Max-Cut943

Samuel B. Hopkins (University of California, Berkeley), Tselil Schramm (Harvard University and MIT), Luca Trevisan (Bocconi University)

Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes954

Mrinalkanti Ghosh (Toyota Technological Institute), Fernando Granha Jeronimo (University of Chicago), Chris Jones (Computer Science Department, University of Chicago, Chicago, USA), Aaron Potechin (University of Chicago), Goutham Rajendran (University of Chicago)

Approximation Algorithms for Stochastic Minimum-Norm Combinatorial Optimization966

Sharat Ibrahimpur (University of Waterloo, Canada), Chaitanya Swamy (University of Waterloo, Canada)


Session 6C

Faster Approximate Pattern Matching: A Unified Approach978

Panagiotis Charalampopoulos (King’s College London, UK and University of Warsaw, Poland), Tomasz Kociumaka (Bar-Ilan University, Israel), Philip Wellnitz (Max Planck Institute for Informatics, Germany)

Edit Distance in Near-Linear Time: It's a Constant Factor990

Alexandr Andoni (Columbia University), Negev Shekel Nosatzki (Columbia University)

Resolution of the Burrows-Wheeler Transform Conjecture1002

Dominik Kempa (University of California, Berkeley, USA), Tomasz Kociumaka (Bar-Ilan University, Ramat Gan, Israel)

Framework for ER-Completeness of Two-Dimensional Packing Problems1014

Mikkel Abrahamsen (University of Copenhagen, Denmark), Tillmann Miltzow (Utrecht University, Netherlands), Nadja Seiferth (Freie Universität Berlin, Germany)

Smoothing the gap Between NP and ER1022

Jeff Erickson (University of Illinois at Urbana-Champaign), Ivor van der Hoog (Utrecht University), Tillmann Miltzow (Utrecht University)

Point Location and Active Learning: Learning Halfspaces Almost Optimally1034

Max Hopkins (University of California, San Diego), Daniel Kane (University of California, San Diego), Shachar Lovett (University of California, San Diego), Gaurav Mahajan (University of California, San Diego)


Session 7A

Explicit near-Fully X-Ramanujan Graphs1045

Ryan O'Donnell (Carnegie Mellon University), Xinyu Wu (Carnegie Mellon University)

Nearly Optimal Pseudorandomness From Hardness1057

Dean Doron (Stanford University, USA), Dana Moshkovitz (UT Austin, USA), Justin Oh (UT Austin, USA), David Zuckerman (UT Austin, USA)

Correlated Pseudorandom Functions from Variable-Density LPN1069

Elette Boyle (IDC Herzliya), Geoffroy Couteau (IRIF), Niv Gilboa (Ben-Gurion University), Yuval Ishai (Technion), Lisa Kohl (Technion), Peter Scholl (Aarhus University)

A Dichotomy for Real Boolean Holant Problems1091

Shuai Shao (University of Wisconsin-Madison, USA), Jin-Yi Cai (University of Wisconsin-Madison, USA)

Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs1103

Jin-Yi Cai (Department of Computer Sciences, University of Wisconsin-Madison), Artsiom Hovarau (Department of Computer Sciences, University of Wisconsin-Madison)


Session 7B

Near-Optimal Decremental SSSP in Dense Weighted Digraphs1112

Aaron Bernstein (Rutgers University New Brunswick), Maximilian Probst Gutenberg (University of Copenhagen and BARC), Christian Wulff-Nilsen (University of Copenhagen and BARC)

Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing1123

Aaron Bernstein (Rutgers University New Brunswick), Maximilian Probst Gutenberg (University of Copenhagen and BARC), Thatchaphol Saranurak (Toyota Technological Institute at Chicago)

Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers1135

Li Chen (Georgia Institute of Technology, USA), Gramoz Goranci (University of Toronto, Canada), Monika Henzinger (University of Vienna, Austria), Richard Peng (Georgia Institute of Technology, USA), Thatchaphol Saranurak (Toyota Technological Institute at Chicago, USA)

Fully-Dynamic Submodular Cover with Bounded Recourse1147

Anupam Gupta (Carnegie Mellon University), Roie Levin (Carnegie Mellon University)

A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond1158

Julia Chuzhoy (Toyota Technological Institute of Chicago), Yu Gao (Georgia Institute of Technology), Jason Li (Carnegie Mellon University), Danupon Nanongkai (KTH Royal Institute of Technology), Richard Peng (Georgia Institute of Technology), Thatchaphol Saranurak (Toyota Technological Institute of Chicago)


Session 7C

Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance1168

Tomasz Kociumaka (Bar-Ilan University, Israel), Barna Saha (University of Calfornia, Berkeley, U.S.)

Testing Linear-Invariant Properties1180

Jonathan Tidor (MIT), Yufei Zhao (MIT)

Testing Positive Semi-Definiteness via Random Submatrices1191

Ainesh Bakshi (Carnegie Mellon University), Rajesh Jayaram (Carnegie Mellon University), Nadiia Chepurko (Massachusetts Institute of Technology)

Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time1203

Mahdi Cheraghchi (University of Michigan, Ann Arbor), Vasileios Nakos (Saarland University and Max-Planck Institute for Informatics)

Pandora's Box with Correlations: Learning and Approximation1214

Shuchi Chawla (University of Wisconsin-Madison, USA), Evangelia Gergatsouli (University of Wisconsin-Madison, USA), Yifeng Teng (University of Wisconsin-Madison, USA), Christos Tzamos (University of Wisconsin-Madison, USA), Ruimin Zhang (University of Chicago, USA)


Session 8A

Extractors and Secret Sharing Against Bounded Collusion Protocols1226

Eshan Chattopadhyay (Cornell University), Jesse Goodman (Cornell University), Vipul Goyal (CMU and NTT Research), Ashutosh Kumar (University of California, Los Angeles), Xin Li (Johns Hopkins University), Raghu Meka (University of California, Los Angeles), David Zuckerman (University of Texas at Austin)

On One-way Functions and Kolmogorov Complexity1243

Yanyi Liu (Cornell University), Rafael Pass (Cornell Tech)

Is it Easier to Prove Theorems that are Guaranteed to be True?1255

Rafael Pass (Cornell Tech), Muthuramakrishnan Venkitasubramaniam (University of Rochester)

A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip1268

Iftach Haitner (Tel Aviv University, Israel), Yonatan Karidi-Heller (Tel Aviv University, Israel)

The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency (Extended Abstract)1277

Benny Applebaum (Tel-Aviv University, Israel), Eliran Kachlon (Tel-Aviv University, Israel), Arpita Patra (Indian Institute of Science, India)

A Constant Rate Non-Malleable Code in the Split-State Model1285

Divesh Aggarwal (National University of Singapore), Maciej Obremski (National University of Singapore)


Session 8B

High-Precision Estimation of Random Walks in Small Space1295

AmirMahdi Ahmadinejad (Amazon), Jon Kelner (MIT), Jack Murtagh (Harvard University), John Peebles (Yale University), Aaron Sidford (Stanford University), Salil Vadhan (Harvard University)

Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction1307

Zongchen Chen (Georgia Institute of Technology, USA), Kuikui Liu (University of Washington, USA), Eric Vigoda (Georgia Institute of Technology, USA)

Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model1319

Nima Anari (Stanford University), Kuikui Liu (University of Washington), Shayan Oveis Gharan (University of Washington)

Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases1331

Nima Anari (Stanford University), Michał Dereziński (University of California, Berkeley)

The Complexity of Approximating Averages on Bounded-Degree Graphs1345

Andreas Galanis (University of Oxford, UK), Daniel Štefankovič (University of Rochester, USA), Eric Vigoda (Georgia Institute of Technology, USA)

Counting Small Induced Subgraphs Satisfying Monotone Properties1356

Marc Roth (Merton College, University of Oxford, United Kingdom), Johannes Schmitt (University of Bonn, Germany), Philip Wellnitz (Max Planck Institute for Informatics, Germany)


Session 8C

Beyond Tree Embeddings - A Deterministic Framework for Network Design with Deadlines or Delay1368

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

Fully Online Matching II: Beating Ranking and Water-Filling1380

Zhiyi Huang (The University of Hong Kong), Zhihao Gavin Tang (Shanghai University of Finance and Economics), Xiaowei Wu (University of Macau), Yuhao Zhang (The University of Hong Kong)

Stochastic Weighted Matching: (1-ε) Approximation1392

Soheil Behnezhad (University of Maryland), Mahsa Derakhshan (University of Maryland)

Optimal Anytime Regret for two Experts1404

Nicholas J. A. Harvey (Department of Computer Science, University of British Columbia), Christopher Liaw (University of British Columbia, Canada), Edwin A. Perkinsy (Department of Mathematics, University of British Columbia), Sikander Randhawa (Department of Computer Science, University of British Columbia)

AdWords in a Panorama1416

Zhiyi Huang (The University of Hong Kong), Qiankun Zhang (The University of Hong Kong), Yuhao Zhang (The University of Hong Kong)

Resolving the Optimal Metric Distortion Conjecture1427

Vasilis Gkatzelis (Drexel University, USA), Daniel Halpern (University of Toronto, Canada), Nisarg Shah (University of Toronto, Canada)