| 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 (Videos) |
Session 1B Chair: Zvika Brakerski (Videos) |
Session 1C Chair: Arnab Bhattacharyya (Videos) |
||
| 10:00-10:20 |
A Better-Than-2 Approximation for Weighted Tree Augmentation
(Full version)
|
Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier
(Full version)
|
Demystifying the border of depth-3 algebraic circuits
(Full version)
|
|
| 10:25-10:45 |
Integer programs with bounded subdeterminants and two nonzeros per row
(Full version)
|
On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds
(Full version)
|
Fooling Constant-Depth Threshold Circuits
(Full version)
|
|
| 10:50-11:10 |
A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations
(Full version)
|
SNARGs for P from LWE
(Full version)
|
Unambiguous DNFs and Alon-Saks-Seymour
(Full version)
|
|
| 11:15-11:35 |
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization
(Full version)
|
Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense `k`-SUM and `k`-XOR
(Full version)
|
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise
(Full version)
|
|
| 11:35-12:00 | Break | |||
| 12:00-13:30 |
Workshop A: Session 1
Recent Directions in Machine Learning (Website) (Videos) |
Workshop B: Session 1
Reflections on Propositional Proofs in Algorithms and Complexity (Website) (Videos) |
Workshop C: Session 1 Workshop on Cryptography (Website) (Videos) |
|
| 13:30-14:00 | Break | |||
| 14:00-15:00 | Business Meeting 1 – Votes Chair: Yuval Rabani |
|||
| Session 2A Chair: Cynthia Vinzant (Videos) |
Session 2B Chair: Barna Saha (Videos) |
Session 2C Chair: Anindya De (Videos) |
||
| 15:00-15:20 |
Rapid mixing of Glauber dynamics via spectral independence for all degrees
(Full version)
|
A Single-Exponential Time 2-Approximation Algorithm for Treewidth
(Full version)
|
An Invariance Principle for the Multi-slice, with Applications
(Full version)
|
|
| 15:25-15:45 |
Spectral Independence via Stability and Applications to Holant-Type Problems
(Full version)
|
Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space
(Full version)
|
Almost Optimal Inapproximability of Multidimensional Packing Problems
(Full version)
|
|
| 15:50-16:10 |
A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings
(Full version)
|
PPSZ is better than you think
(Full version)
|
Applications of random algebraic constructions to hardness of approximation
(Full version)
|
|
| 16:15-16:35 |
Towards the sampling Lovász Local Lemma
(Full version)
|
At most `3.55^n` stable matchings
(Full version)
|
||
| 16:35-17:00 | Break | |||
| 17:00-18:30 |
Workshop A: Session 2
Recent Directions in Machine Learning (Website) (Videos) |
Workshop B: Session 2
Reflections on Propositional Proofs in Algorithms and Complexity (Website) (Videos) |
Workshop C: Session 2 Workshop on Cryptography (Website) (Videos) |
|
| Day 2: Tuesday February 8, 2022 | ||||
| Session 3A Chair: Johan Hastad (Videos) |
Session 3B Chair: Piyush Srivastava (Videos) |
Session 3C Chair: R. Ravi (Videos) |
||
| 10:00-10:20 |
Random walks and forbidden minors III: poly`(d\epsilon^{-1})`-time partition oracles for minor-free graph classes
(Full version)
|
The Algorithmic Phase Transition of Random `k`-SAT for Low Degree Polynomials
(Full version)
|
Approximating Maximum Independent Set for Rectangles in the Plane
(Full version)
|
|
| 10:25-10:45 |
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model
(Full version)
|
One-step replica symmetry breaking of random regular NAE-SAT
(Full version)
|
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
(Full version)
|
|
| 10:50-11:10 |
Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies
(Full version)
|
Sharp Thresholds in Random Simple Temporal Graphs
(Full version)
|
Optimal Approximate Distance Oracle for Planar Graphs
(Full version)
|
|
| 11:15-11:35 |
Testability of relations between permutations
(Full version)
|
Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron
(Full version)
|
Covering Polygons is Even Harder
(Full version)
|
|
| 11:35-12:00 | Break | |||
| 12:00-13:30 |
Workshop A: Session 3
Recent Directions in Machine Learning (Website) (Videos) |
Workshop B: Session 3
Reflections on Propositional Proofs in Algorithms and Complexity (Website) (Videos) |
Workshop C: Session 3 Workshop on Cryptography (Website) (Videos) |
|
| 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 (Videos) |
Session 4B Chair: Pritish Kamath (Videos) |
Session 4C Chair: R. Ravi (Videos) |
||
| 15:00-15:20 |
Robust Recovery for Stochastic Block Models
(Full version)
|
The Minimum Formula Size Problem is (ETH) Hard
(Full version)
|
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor
(Full version)
|
|
| 15:25-15:45 |
On statistical inference when fixed points of belief propagation are unstable
(Full version)
|
The Hardest Explicit Construction
(Full version)
|
Embeddings of Planar Quasimetrics into Directed `ℓ_1` and Polylogarithmic Approximation for Directed Sparsest-Cut
(Full version)
|
|
| 15:50-16:10 |
Sum-of-Squares Lower Bounds for Sparse Independent Set
(Full version)
|
Tradeoffs for small-depth Frege proofs
(Full version)
|
Hop-Constrained Metric Embeddings and their Applications
(Full version)
|
|
| 16:15-16:35 |
Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models
(Full version)
|
Group isomorphism is nearly-linear time for most orders
(Full version)
|
A Hitting Set Relaxation for `k`-Server and an Extension to Time-Windows
(Full version)
|
|
| 16:35-17:00 | Break | |||
| 17:00-18:30 |
Workshop A: Session 4
Recent Directions in Machine Learning (Website) (Videos) |
Workshop B: Session 4
Reflections on Propositional Proofs in Algorithms and Complexity (Website) (Videos) |
Workshop C: Session 4 Workshop on Cryptography (Website) (Videos) |
|
| Day 3: Wednesday February 9, 2022 | ||||
| Session 5A Chair: R. Ravi (Videos) |
Session 5B Chair: Ankit Garg (Videos) |
Session 5C Chair: Piyush Srivastava (Videos) |
||
| 10:00-10:20 |
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao
(Full version)
|
Quantum learning algorithms imply circuit lower bounds
(Full version)
|
Improved Extractors for Small-Space Sources
(Full version)
|
|
| 10:25-10:45 |
Faster Sparse Minimum Cost Flow by Electrical Flow Localization
(Full version)
|
Exponential Separations Between Learning With and Without Quantum Memory
(Full version)
|
Affine Extractors for Almost Logarithmic Entropy
(Full version)
|
|
| 10:50-11:10 |
2-Norm Flow Diffusion in Near-Linear Time
(Full version)
|
Quantum soundness of testing tensor codes
(Full version)
|
Tight Bounds for General Computation in Noisy Broadcast Networks
(Full version)
|
|
| 11:15-11:35 |
On the Power of Preconditioning in Sparse Linear Regression
(Full version)
|
Quasi-polynomial time approximation of output probabilities of geometrically-local, shallow quantum circuits.
(Full version)
|
Constructive Separations and Their Consequences
(Full version)
|
|
| 11:35-12:00 | Break | |||
| Session 6A Chair: Pritish Kamath (Videos) |
Session 6B Chair: Arnab Bhattacharyya (Videos) |
Session 6C Chair: Russell Impagliazzo (Videos) |
||
| 12:00-12:20 |
A Theory of PAC Learnability of Partial Concept Classes
(Full version)
|
Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings
(Full version)
|
On Worst-Case Learning in Relativized Heuristica
(Full version)
|
|
| 12:25-12:45 |
Optimal Sub-Gaussian Mean Estimation in R
(Full version)
|
List-decodability with large radius for Reed-Solomon codes
(Full version)
|
Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms
(Full version)
|
|
| 12:50-13:10 |
Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination
(Full version)
|
The zero-rate threshold for adversarial bit-deletions is less than 1/2
(Full version)
|
LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic
(Full version)
|
|
| 13:15-13:35 |
Learning Deep ReLU Networks Is Fixed-Parameter Tractable
(Full version)
|
Exponential Lower Bounds for Locally Decodable Codes Correcting Insertions and Deletions
(Full version)
|
On Classifying Continuous Constraint Satisfaction problems
(Full version)
|
|
| 13:35-14:00 | Break | |||
| Session 7: Plenary Session Chair: Nisheeth Vishnoi (Videos) |
||||
| 14:00-14:30 |
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance
(Full version)
|
|||
| 14:30-15:00 |
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
(Full version)
|
|||
| 15:00-15:25 | Break | |||
| Session 8A Chair: Laci Vegh (Videos) |
Session 8B Chair: R. Ravi (Videos) |
Session 8C Chair: Anindya De (Videos) |
||
| 15:25-15:45 |
Combinatorial Contracts
(Full version)
|
Fully Dynamic `s`-`t` Edge Connectivity in Subpolynomial Time
(Full version)
|
Statistically Near-Optimal Hypothesis Selection
(Full version)
|
|
| 15:50-16:10 |
FIXP-membership via Convex Optimization: Games, Cakes, and Markets
(Full version)
|
Time-Optimal Sublinear Algorithms for Matching and Vertex Cover
(Full version)
|
Properly learning decision trees in almost polynomial time
(Full version)
|
|
| 16:15-16:35 |
On the Nisan-Ronen conjecture
(Full version)
|
Small space and streaming pattern matching with `k` edits
(Full version)
|
Sharper bounds on the Fourier concentration of DNFs
(Full version)
|
|
| 16:40-17:00 |
Continuity, Uniqueness and Long-Term Behavior of Nash Flows Over Time
(Full version)
|
A Quantum Advantage for a Natural Streaming Problem
(Full version)
|
||
| Day 4: Thursday February 10, 2022 | ||||
| Session 9A Chair: Pritish Kamath (Videos) |
Session 9B Chair: R. Ravi (Videos) |
Session 9C Chair: Susanna Rezende (Videos) |
||
| 10:00-10:20 |
Smoothed Analysis with Adaptive Adversaries
(Full version)
|
Minor Sparsifiers and the Distributed Laplacian Paradigm
(Full version)
|
MAJORITY-3SAT (and Related Problems) in Polynomial Time
(Full version)
|
|
| 10:25-10:45 |
Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling
(Full version)
|
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time
(Full version)
|
A time and space optimal stable population protocol solving exact majority
(Full version)
|
|
| 10:50-11:10 |
Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning
(Full version)
|
Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition
(Full version)
|
Stochastic and Worst-Case Generalized Sorting Revisited
(Full version)
|
|
| 11:15-11:35 |
Feature Purification: How Adversarial Training Performs Robust Deep Learning
(Full version)
|
Hardness of approximate Diameter: now for undirected graphs
(Full version)
|
Tight Space Complexity of the Coin Problem
(Full version)
|
|
| 11:35-12:00 | Break | |||
| Session 10A Chair: J. Grochow (Videos) |
Session 10B Chair: R. Ravi (Videos) |
Session 10C Chair: Ravi Kumar (Videos) |
||
| 12:00-12:20 |
A proof of the Erdős-Faber-Lovász conjecture: Algorithmic aspects
(Full version)
|
A Nearly Optimal All Pairs Minimum Cuts Algorithm in Simple Graphs
(Full version)
|
Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering
(Full version)
|
|
| 12:25-12:45 |
New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems
(Full version)
|
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time
(Full version)
|
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
(Full version)
|
|
| 12:50-13:10 |
The supersingular isogeny path and endomorphism ring problems are equivalent
(Full version)
|
Minimum Cuts in Directed Graphs via Partial Sparsification
(Full version)
|
Approximability of all finite CSPs with linear sketches
(Full version)
|
|
| 13:15-13:35 |
Harmonic Persistent Homology
(Full version)
|
Spectral Hypergraph Sparsifiers of Nearly Linear Size
(Full version)
|
Terminal Embeddings in Sublinear Time
(Full version)
|
|
| 13:35-14:00 | Break | |||
| Session 11A Chair: Russell Impagliazzo (Videos) |
Session 11B Chair: R. Ravi (Videos) |
Session 11C Chair: David Gosset (Videos) |
||
| 14:00-14:20 |
Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography
(Full version)
|
Random Order Set Cover is as Easy as Offline
(Full version)
|
A direct product theorem for quantum communication complexity with applications to device-independent QKD
(Full version)
|
|
| 14:25-14:45 |
Reachability in Vector Addition Systems is Ackermann-complete
(Full version)
|
Improved Online Correlated Selection
(Full version)
|
Quantum supremacy and hardness of estimating output probabilities of quantum circuits
(Full version)
|
|
| 14:50-15:10 |
The Reachability Problem for Petri Nets is Not Primitive Recursive
(Full version)
|
Multiway Online Correlated Selection
(Full version)
|
Noise and the frontier of quantum supremacy
(Full version)
|
|
| 15:10-17:00 | Business Meeting 2 – Reports Sessions Chair: Yuval Rabani |
|||
| Conference Ends | ||||