IEEE FOCS 2021 Program
All times are in Eastern Standard Time (US East Coast/New York time)
Day 1: Monday February 7, 2022
9:30-10:00  Welcome to IEEE FOCS 2021
Chair: Alexandra Kolla
  Session 1A
Chair: R. Ravi
Session 1B
Chair: Zvika Brakerski
Session 1C
Chair: Arnab Bhattacharyya
10:00-10:20  A Better-Than-2 Approximation for Weighted Tree Augmentation (Full version)
Vera Traub and Rico Zenklusen
Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier (Full version)
Alessandro Chiesa, Fermi Ma, Nicholas Spooner and Mark Zhandry
Demystifying the border of depth-3 algebraic circuits (Full version)
Pranjal Dutta, Prateek Dwivedi and Nitin Saxena
10:25-10:45  Integer programs with bounded subdeterminants and two nonzeros per row (Full version)
Samuel Fiorini, Gwenaël Joret, Stefan Weltge and Yelena Yuditsky
On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds (Full version)
Nai-Hui Chia, Kai-Min Chung, Qipeng Liu and Takashi Yamakawa
Fooling Constant-Depth Threshold Circuits (Full version)
Pooya Hatami, William Hoza, Avishay Tal and Roei Tell
10:50-11:10  A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations (Full version)
Wenzheng Li and Jan Vondrak
SNARGs for P from LWE (Full version)
Arka Rai Choudhuri, Abhishek Jain and Zhengzhong Jin
Unambiguous DNFs and Alon-Saks-Seymour (Full version)
Mika Göös, Shalev Ben-David, Robin Kothari, Siddhartha Jain and Kaspars Balodis
11:15-11:35  A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization (Full version)
Deeparnab Chakrabarty, Yu Chen and Sanjeev Khanna
Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense `k`-SUM and `k`-XOR (Full version)
Itai Dinur, Nathan Keller and Ohad Klein
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise (Full version)
Lijie Chen and Roei Tell
11:35-12:00  Break
12:00-13:30  Workshop A: Session 1
Recent Directions in Machine Learning
Workshop B: Session 1
Reflections on Propositional Proofs in Algorithms and Complexity
Workshop C: Session 1
Workshop on Cryptography
13:30-14:00  Break
14:00-15:00  Business Meeting 1 – Votes
Chair: Yuval Rabani
  Session 2A
Chair: Cynthia Vinzant
Session 2B
Chair: Barna Saha
Session 2C
Chair: Anindya De
15:00-15:20  Rapid mixing of Glauber dynamics via spectral independence for all degrees (Full version)
Xiaoyu Chen, Weiming Feng, Yitong Yin and Xinyuan Zhang
A Single-Exponential Time 2-Approximation Algorithm for Treewidth (Full version)
Tuukka Korhonen
An Invariance Principle for the Multi-slice, with Applications (Full version)
Mark Braverman, Subhash Khot, Noam Lifshitz and Dor Minzer
15:25-15:45  Spectral Independence via Stability and Applications to Holant-Type Problems (Full version)
Zongchen Chen, Kuikui Liu and Eric Vigoda
Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space (Full version)
Hans L. Bodlaender, Carla Groenland, Jesper Nederlof and Celine M. F. Swennenhuis
Almost Optimal Inapproximability of Multidimensional Packing Problems (Full version)
Sai Sandeep
15:50-16:10  A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings (Full version)
Dorna Abdolazimi, Kuikui Liu and Shayan Oveis Gharan
PPSZ is better than you think (Full version)
Dominik Scheder
Applications of random algebraic constructions to hardness of approximation (Full version)
Boris Bukh, Karthik C. S. and Bhargav Narayanan
16:15-16:35  Towards the sampling Lovász Local Lemma (Full version)
Vishesh Jain, Huy Tuan Pham and Thuy-Duong Vuong
At most `3.55^n` stable matchings (Full version)
Cory Palmer and Dömötör Pálvölgyi
16:35-17:00  Break
17:00-18:30  Workshop A: Session 2
Recent Directions in Machine Learning
Workshop B: Session 2
Reflections on Propositional Proofs in Algorithms and Complexity
Workshop C: Session 2
Workshop on Cryptography
Day 2: Tuesday February 8, 2022
  Session 3A
Chair: Johan Hastad
Session 3B
Chair: Piyush Srivastava
Session 3C
Chair: R. Ravi
10:00-10:20  Random walks and forbidden minors III: poly`(d\epsilon^{-1})`-time partition oracles for minor-free graph classes (Full version)
Akash Kumar, C. Seshadhri and Andrew Stolman
The Algorithmic Phase Transition of Random `k`-SAT for Low Degree Polynomials (Full version)
Guy Bresler and Brice Huang
Approximating Maximum Independent Set for Rectangles in the Plane (Full version)
Joseph Mitchell
10:25-10:45  Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model (Full version)
Oded Goldreich and Avi Wigderson
One-step replica symmetry breaking of random regular NAE-SAT (Full version)
Danny Nam, Allan Sly and Youngtak Sohn
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP (Full version)
Sándor Kisfaludi-Bak, Jesper Nederlof and Karol Węgrzycki
10:50-11:10  Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies (Full version)
Marco Bressan and Marc Roth
Sharp Thresholds in Random Simple Temporal Graphs (Full version)
Arnaud Casteigts, Mikhail Raskin, Malte Renken and Viktor Zamaraev
Optimal Approximate Distance Oracle for Planar Graphs (Full version)
Hung Le and Christian Wulff-Nilsen
11:15-11:35  Testability of relations between permutations (Full version)
Oren Becker, Alexander Lubotzky and Jonathan Mosheiff
Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron (Full version)
Emmanuel Abbe, Shuangping Li and Allan Sly
Covering Polygons is Even Harder (Full version)
Mikkel Abrahamsen
11:35-12:00  Break
12:00-13:30  Workshop A: Session 3
Recent Directions in Machine Learning
Workshop B: Session 3
Reflections on Propositional Proofs in Algorithms and Complexity
Workshop C: Session 3
Workshop on Cryptography
13:30-14:30  Break Junior-Senior Lunch (Signup)
14:30-15:00  Test of Time Awards Presentation
Chair: Yuval Rabani
  Session 4A
Chair: Anindya De
Session 4B
Chair: Pritish Kamath
Session 4C
Chair: R. Ravi
15:00-15:20  Robust Recovery for Stochastic Block Models (Full version)
Jingqiu Ding, Tommaso D’Orsi, Rajai Nasser and David Steurer
The Minimum Formula Size Problem is (ETH) Hard (Full version)
Rahul Ilango
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor (Full version)
Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis and Mikkel Thorup
15:25-15:45  On statistical inference when fixed points of belief propagation are unstable (Full version)
Siqi Liu, Sidhanth Mohanty and Prasad Raghavendra
The Hardest Explicit Construction (Full version)
Oliver Korten
Embeddings of Planar Quasimetrics into Directed `ℓ_1` and Polylogarithmic Approximation for Directed Sparsest-Cut (Full version)
Ken-Ichi Kawarabayashi and Anastasios Sidiropoulos
15:50-16:10  Sum-of-Squares Lower Bounds for Sparse Independent Set (Full version)
Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani and Jeff Xu
Tradeoffs for small-depth Frege proofs (Full version)
Toniann Pitassi, Prasanna Ramakrishnan and Li-Yang Tan
Hop-Constrained Metric Embeddings and their Applications (Full version)
Arnold Filtser
16:15-16:35  Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models (Full version)
Enric Boix-Adserà, Guy Bresler and Frederic Koehler
Group isomorphism is nearly-linear time for most orders (Full version)
James Wilson and Heiko Dietrich
A Hitting Set Relaxation for `k`-Server and an Extension to Time-Windows (Full version)
Anupam Gupta, Amit Kumar and Debmalya Panigrahi
16:35-17:00  Break
17:00-18:30  Workshop A: Session 4
Recent Directions in Machine Learning
Workshop B: Session 4
Reflections on Propositional Proofs in Algorithms and Complexity
Workshop C: Session 4
Workshop on Cryptography
Day 3: Wednesday February 9, 2022
  Session 5A
Chair: R. Ravi
Session 5B
Chair: Ankit Garg
Session 5C
Chair: Piyush Srivastava
10:00-10:20  Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao (Full version)
Yu Gao, Yang P. Liu and Richard Peng
Quantum learning algorithms imply circuit lower bounds (Full version)
Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira and Aarthi Sundaram
Improved Extractors for Small-Space Sources (Full version)
Eshan Chattopadhyay and Jesse Goodman
10:25-10:45  Faster Sparse Minimum Cost Flow by Electrical Flow Localization (Full version)
Kyriakos Axiotis, Aleksander Mądry and Adrian Vladu
Exponential Separations Between Learning With and Without Quantum Memory (Full version)
Sitan Chen, Jordan Cotler, Hsin-Yuan Huang and Jerry Li
Affine Extractors for Almost Logarithmic Entropy (Full version)
Eshan Chattopadhyay, Jesse Goodman and Jyun-Jie Liao
10:50-11:10  2-Norm Flow Diffusion in Near-Linear Time (Full version)
Li Chen, Richard Peng and Di Wang
Quantum soundness of testing tensor codes (Full version)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen
Tight Bounds for General Computation in Noisy Broadcast Networks (Full version)
Klim Efremenko, Gillat Kol, Dmitry Paramonov and Raghuvansh Saxena
11:15-11:35  On the Power of Preconditioning in Sparse Linear Regression (Full version)
Jonathan Kelner, Frederic Koehler, Raghu Meka and Dhruv Rohatgi
Quasi-polynomial time approximation of output probabilities of geometrically-local, shallow quantum circuits. (Full version)
Matthew Coudron and Nolan Coble
Constructive Separations and Their Consequences (Full version)
Lijie Chen, Ce Jin, Rahul Santhanam and Ryan Williams
11:35-12:00  Break
  Session 6A
Chair: Pritish Kamath
Session 6B
Chair: Arnab Bhattacharyya
Session 6C
Chair: Russell Impagliazzo
12:00-12:20  A Theory of PAC Learnability of Partial Concept Classes (Full version)
Noga Alon, Steve Hanneke, Ron Holzman and Shay Moran
Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings (Full version)
Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo and Mary Wootters
On Worst-Case Learning in Relativized Heuristica (Full version)
Shuichi Hirahara and Mikito Nanashima
12:25-12:45  Optimal Sub-Gaussian Mean Estimation in R (Full version)
Jasper C.H. Lee and Paul Valiant
List-decodability with large radius for Reed-Solomon codes (Full version)
Asaf Ferber, Matthew Kwan and Lisa Sauermann
Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms (Full version)
Robert Robere and Jeroen Zuiddam
12:50-13:10  Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination (Full version)
Sitan Chen, Frederic Koehler, Ankur Moitra and Morris Yau
The zero-rate threshold for adversarial bit-deletions is less than 1/2 (Full version)
Venkatesan Guruswami, Xiaoyu He and Ray Li
LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic (Full version)
Marco Carmosino, Valentine Kabanets, Antonina Kolokolova and Igor C. Oliveira
13:15-13:35  Learning Deep ReLU Networks Is Fixed-Parameter Tractable (Full version)
Sitan Chen, Adam Klivans and Raghu Meka
Exponential Lower Bounds for Locally Decodable Codes Correcting Insertions and Deletions (Full version)
Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng and Minshen Zhu
On Classifying Continuous Constraint Satisfaction problems (Full version)
Till Miltzow and Reinier Schmiermann
13:35-14:00  Break
  Session 7: Plenary Session
Chair: Nisheeth Vishnoi
14:00-14:30  Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance (Full version)
Xiao Mao
14:30-15:00  Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits (Full version)
Nutan Limaye, Srikanth Srinivasan and Sébastien Tavena
15:00-15:25  Break
  Session 8A
Chair: Laci Vegh
Session 8B
Chair: R. Ravi
Session 8C
Chair: Anindya De
15:25-15:45  Combinatorial Contracts (Full version)
Paul Dutting, Tomer Ezra, Michal Feldman and Thomas Kesselheim
Fully Dynamic `s`-`t` Edge Connectivity in Subpolynomial Time (Full version)
Wenyu Jin and Xiaorui Sun
Statistically Near-Optimal Hypothesis Selection (Full version)
Olivier Bousquet, Mark Braverman, Klim Efremenko, Gillat Kol and Shay Moran
15:50-16:10  FIXP-membership via Convex Optimization: Games, Cakes, and Markets (Full version)
Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh and Alexandros Hollender
Time-Optimal Sublinear Algorithms for Matching and Vertex Cover (Full version)
Soheil Behnezhad
Properly learning decision trees in almost polynomial time (Full version)
Guy Blanc, Jane Lange, Mingda Qiao and Li-Yang Tan
16:15-16:35  On the Nisan-Ronen conjecture (Full version)
George Christodoulou, Elias Koutsoupias and Annamaria Kovacs
Small space and streaming pattern matching with `k` edits (Full version)
Tomasz Kociumaka, Ely Porat and Tatiana Starikovskaya
Sharper bounds on the Fourier concentration of DNFs (Full version)
Victor Lecomte and Li-Yang Tan
16:40-17:00  Continuity, Uniqueness and Long-Term Behavior of Nash Flows Over Time (Full version)
Neil Olver, Leon Sering and Laura Vargas Koch
A Quantum Advantage for a Natural Streaming Problem (Full version)
John Kallaugher
Day 4: Thursday February 10, 2022
  Session 9A
Chair: Pritish Kamath
Session 9B
Chair: R. Ravi
Session 9C
Chair: Susanna Rezende
10:00-10:20  Smoothed Analysis with Adaptive Adversaries (Full version)
Nika Haghtalab, Tim Roughgarden and Abhishek Shetty
Minor Sparsifiers and the Distributed Laplacian Paradigm (Full version)
Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun and Mingquan Ye
MAJORITY-3SAT (and Related Problems) in Polynomial Time (Full version)
Shyan Akmal and Ryan Williams
10:25-10:45  Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling (Full version)
Vitaly Feldman, Audra McMillan and Kunal Talwar
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time (Full version)
Aaron Bernstein, Maximilian Probst Gutenberg and Thatchaphol Saranurak
A time and space optimal stable population protocol solving exact majority (Full version)
David Doty, Mahsa Eftekhari Hesari, Leszek Gąsieniec, Eric Severson, Grzegorz Stachowiak and Przemysław Uznański
10:50-11:10  Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning (Full version)
Yuanzhi Li, Ruosong Wang and Lin Yang
Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition (Full version)
Mohsen Ghaffari and Fabian Kuhn
Stochastic and Worst-Case Generalized Sorting Revisited (Full version)
William Kuszmaul and Shyam Narayanan
11:15-11:35  Feature Purification: How Adversarial Training Performs Robust Deep Learning (Full version)
Zeyuan Allen-Zhu and Yuanzhi Li
Hardness of approximate Diameter: now for undirected graphs (Full version)
Mina Dalirrooyfard, Ray Li and Virginia Vassilevska Williams
Tight Space Complexity of the Coin Problem (Full version)
Mark Braverman, Sumegha Garg and Or Zamir
11:35-12:00  Break
  Session 10A
Chair: J. Grochow
Session 10B
Chair: R. Ravi
Session 10C
Chair: Ravi Kumar
12:00-12:20  A proof of the Erdős-Faber-Lovász conjecture: Algorithmic aspects (Full version)
Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku and Deryk Osthus
A Nearly Optimal All Pairs Minimum Cuts Algorithm in Simple Graphs (Full version)
Jason Li, Debmalya Panigrahi and Thatchaphol Saranurak
Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering (Full version)
Michael A. Bender, Bradley C. Kuszmaul and William Kuszmaul
12:25-12:45  New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems (Full version)
Guillaume Moroz
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time (Full version)
Amir Abboud, Robert Krauthgamer and Ohad Trabelsi
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators (Full version)
David P. Woodruff and Samson Zhou
12:50-13:10  The supersingular isogeny path and endomorphism ring problems are equivalent (Full version)
Benjamin Wesolowski
Minimum Cuts in Directed Graphs via Partial Sparsification (Full version)
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Kent Quanrud and Thatchaphol Saranurak
Approximability of all finite CSPs with linear sketches (Full version)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan and Santhoshini Velusamy
13:15-13:35  Harmonic Persistent Homology (Full version)
Saugata Basu and Nathanael Cox
Spectral Hypergraph Sparsifiers of Nearly Linear Size (Full version)
Michael Kapralov, Robert Krauthgamer, Jakab Tardos and Yuichi Yoshida
Terminal Embeddings in Sublinear Time (Full version)
Yeshwanth Cherapanamjeri and Jelani Nelson
13:35-14:00  Break
  Session 11A
Chair: Russell Impagliazzo
Session 11B
Chair: R. Ravi
Session 11C
Chair: David Gosset
14:00-14:20  Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography (Full version)
Kyle Burke, Matthew Ferland and Shang-Hua Teng
Random Order Set Cover is as Easy as Offline (Full version)
Anupam Gupta, Gregory Kehne and Roie Levin
A direct product theorem for quantum communication complexity with applications to device-independent QKD (Full version)
Rahul Jain and Srijita Kundu
14:25-14:45  Reachability in Vector Addition Systems is Ackermann-complete (Full version)
Wojciech Czerwiński and Łukasz Orlikowski
Improved Online Correlated Selection (Full version)
Ruiquan Gao, Zhongtian He, Zhiyi Huang, Zipei Nie, Bijun Yuan and Yan Zhong
Quantum supremacy and hardness of estimating output probabilities of quantum circuits (Full version)
Yasuhiro Kondo, Ryuhei Mori and Ramis Movassagh
14:50-15:10  The Reachability Problem for Petri Nets is Not Primitive Recursive (Full version)
Jérôme Leroux
Multiway Online Correlated Selection (Full version)
Guy Blanc and Moses Charikar
Noise and the frontier of quantum supremacy (Full version)
Adam Bouland, Bill Fefferman, Zeph Landau and Yunchao Liu
15:10-17:00  Business Meeting 2 – Reports Sessions
Chair: Yuval Rabani
  Conference Ends