| IEEE FOCS 2022 Program | |||||||
| All times are in Mountain Standard Time (floorplan link) |
|||||||
| Day 1: Monday October 31, 2022 | |||||||
| Session 1A Colorado A-B |
Session 1B Colorado C-D |
Session 1C Colorado E |
|||||
| 09:00-09:20 |
Binary Codes with Resilience Beyond 1/4 via Interaction
|
Classical Verification of Quantum Computations in Linear Time
(full version) |
Properly learning monotone functions via local correction
(full version) |
||||
| 09:25-09:45 |
Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits
(full version) |
Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography
(full version) |
Testing Positive Semidefiniteness Using Linear Measurements
(full version) |
||||
| 09:50-10:10 |
Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring
(full version) |
Tight Bounds for Quantum State Certification with Incoherent Measurements
(full version) |
Improved Optimal Testing Results from Global Hypercontractivity
(full version) |
||||
| 10:15-10:35 |
Punctured Low-Bias Codes Behave Like Random Linear Codes
(full version) |
Verifiable Quantum Advantage without Structure
(full version) |
|||||
| 10:35-11:00 | Break | ||||||
| 11:00-12:30 |
Workshop A: Session 1 Colorado A-B Advances on Metric Embeddings |
Workshop B: Session 1 Colorado C-D New Directions in Derandomization |
Workshop C: Session 1 Colorado E Fair Division: Algorithms and Complexity |
||||
| 12:30-14:00 | Lunch | ||||||
| Session 2A Colorado A-B |
Session 2B Colorado C-D |
Session 2C Colorado E |
|||||
| 14:00-14:20 |
Localization schemes: A framework for proving mixing bounds for Markov chains
(full version) |
Pure-Circuit: Strong Inapproximability for PPAD
|
Simple Hard Instances for Low-Depth Algebraic Proofs
(full version) |
||||
| 14:25-14:45 |
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence
(full version) |
Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design
(full version) |
Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits
(full version) |
||||
| 14:50-15:10 |
Optimal learning of quantum Hamiltonians from high-temperature Gibbs states
(full version) |
First Price Auction is 1 - 1 / e2 Efficient
(full version) |
Radical Sylvester-Gallai Theorem for Cubics
|
||||
| 15:15-15:35 |
Sampling Lovasz Local Lemma For General Constraint Satisfaction Solutions In Near-Linear Time
(full version) |
Fast Multivariate Multipoint Evaluation Over All Finite Fields
(full version) |
|||||
| 15:35-16:00 | Break | ||||||
| 16:00-17:30 |
Workshop A: Session 2 Colorado A-B Advances on Metric Embeddings |
Workshop B: Session 2 Colorado C-D New Directions in Derandomization |
Workshop C: Session 2 Colorado E Fair Division: Algorithms and Complexity |
||||
| Day 2: Tuesday November 1, 2022 | |||||||
| Session 3A Colorado A-B |
Session 3B Colorado C-D |
Session 3C Colorado E |
|||||
| 09:00-09:20 |
Solving SDP Faster: A Robust IPM Framework and Efficient Implementation
(full version) |
Survivable Network Design Revisited: Group-Connectivity
(full version) |
Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses
(full version) |
||||
| 09:25-09:45 |
Improved Lower Bounds for Submodular Function Minimization
(full version) |
Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles
(full version) |
Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization
(full version) |
||||
| 09:50-10:10 |
Determinant Maximization via Matroid Intersection Algorithms
(full version) |
Fitting Metrics and Ultrametrics with Minimum Disagreements
(full version) |
Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
(full version) |
||||
| 10:15-10:35 |
Interior point methods are not worse than Simplex
(full version) |
Algorithms for the ferromagnetic Potts model on expanders
(full version)
|
|||||
| 10:35-11:00 | Break | ||||||
| 11:00-12:30 |
Workshop A: Session 3 Colorado A-B Advances on Metric Embeddings |
Workshop B: Session 3 Colorado C-D New Directions in Derandomization |
Workshop D: Session 1 Colorado E Privacy Preserving Machine Learning |
||||
| 12:30-14:00 | Lunch | ||||||
| Plenary Session Colorado E |
|||||||
| 14:00-14:45 |
Knuth Prize Lecture
|
||||||
| 14:50-15:20 |
On Matrix Multiplication and Polynomial Identity Testing
(full version) |
||||||
| 15:20-16:00 | Break | ||||||
| 16:00-17:30 |
Workshop A: Session 4 Colorado A-B Advances on Metric Embeddings |
Workshop B: Session 4 Colorado C-D New Directions in Derandomization |
Workshop D: Session 2 Colorado E Privacy Preserving Machine Learning |
||||
| 17:30-18:00 | Break | ||||||
| 18:00-19:30 | Business Meeting Colorado E |
||||||
| Day 3: Wednesday November 2, 2022 | |||||||
| Session 4A Colorado A-B |
Session 4B Colorado C-D |
Session 4C Colorado E |
|||||
| 09:00-09:20 |
Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues
(full version) |
Using invariant theory to fool polynomials
|
Local Computation of Maximal Independent Set
|
||||
| 09:25-09:45 |
Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
|
Derandomizing Directed Random Walks in Almost-Linear Time
(full version) |
Streaming Facility Location in High Dimension via Geometric Hashing
(full version) |
||||
| 09:50-10:10 |
Motif Cut Sparsifiers
(full version) |
Linear Hashing with ℓ∞ guarantees and two-sided Kakeya bounds
(full version) |
The Power of Uniform Sampling for Coresets
(full version) |
||||
| 10:15-10:35 |
Unstructured Hardness to Average-Case Randomness
(full version) |
On Weighted Graph Sparsification by Linear Sketching
(full version) |
|||||
| 10:35-11:00 | Break | ||||||
| Session 5A Colorado A-B |
Session 5B Colorado C-D |
Session 5C Colorado E |
|||||
| 11:00-11:20 |
Factorial Lower Bounds for (Almost) Random Order Streams
(full version) |
Induced Cycles and Paths Are Harder Than You Think
(full version) |
Sparse random hypergraphs: Non-backtracking spectra and community detection
(full version) |
||||
| 11:25-11:45 |
The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut
(full version) |
Hardness Self-Amplification from Feasible Hard-Core Sets
(full version) |
Algorithms and Barriers in the Symmetric Binary Perceptron Model
(full version) |
||||
| 11:50-12:10 |
Cut Query Algorithms with Star Contraction
(full version) |
A tight (non-combinatorial) conditional lower bound for Klee's Measure Problem in 3D
|
Optimal mixing for two-state anti-ferromagnetic spin systems
(full version) |
||||
| 12:15-12:35 |
Memory Bounds for Learning
(full version) |
||||||
| 12:35-14:00 | Lunch | ||||||
| Session 6 (Plenary) Colorado E |
|||||||
| 14:00-14:30 |
Negative-Weight Single-Source Shortest Paths in Near-Linear Time
(full version) |
||||||
| 14:35-15:05 |
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
(full version) |
||||||
| 15:05-16:00 | Break | ||||||
| Session 7A Colorado A-B |
Session 7B Colorado C-D |
Session 7C Colorado E |
|||||
| 16:00-16:20 |
Randomised Composition and Small-Bias Minimax
(full version) |
Correlation Clustering with Sherali-Adams
(full version) |
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
(full version) |
||||
| 16:25-16:45 |
A Proof of the Kahn-Kalai Conjecture
(full version) |
Explicit Lower Bounds Against Ω(n)-Rounds of Sum-of-Squares
(full version) |
Õ(n + poly(k))-time Algorithm for Distance k Tree Edit Distance
|
||||
| 16:50-17:10 |
On the Range Avoidance Problem for Circuits
(full version) |
Faster Pattern Matching under Edit Distance
(full version) |
|||||
| 17:10-18:00 | Break | ||||||
| 18:00-19:30 | Reception Colorado Prefunction |
TCS Women Mentoring Panel Colorado E |
|||||
| Day 4: Thursday November 3, 2022 | |||||||
| Session 8A Colorado A-B |
Session 8B Colorado C-D |
Session 8C Colorado E |
|||||
| 09:00-09:20 |
Estimating the Longest Increasing Subsequence in Nearly Optimal Time
(full version) |
Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Outdegree Ordering, and Densest Subgraphs
|
Balanced Allocations: The Heavily Loaded Case with Deletions
(full version) |
||||
| 09:25-09:45 |
Almost 3-Approximate Correlation Clustering in Constant Rounds
(full version) |
Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets
|
Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing
(full version) |
||||
| 09:50-10:10 |
High-Dimensional Geometric Streaming in Polynomial Space
(full version) |
New Additive Spanner Lower Bounds by an Unlayered Obstacle Product
(full version) |
Minimax Rates for Robust Community Detection
(full version) |
||||
| 10:15-10:35 |
Active Linear Regression for ℓp Norms and Beyond
(full version) |
Deterministic Small Vertex Connectivity in Almost Linear Time
|
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP
(full version) |
||||
| 10:35-11:00 | Break | ||||||
| Session 9A Colorado A-B |
Session 9B Colorado C-D |
Session 9C Colorado E |
|||||
| 11:00-11:20 |
Generalised entropy accumulation
(full version) |
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time
(full version) |
Planting Undetectable Backdoors in Machine Learning Models
(full version) |
||||
| 11:25-11:45 |
Post-Quantum Zero Knowledge, Revisited (or: How to Do Quantum Rewinding Undetectably)
(full version) |
Constant Approximation of Min-Distances in Near-Linear Time
|
A Characterization of Multiclass Learnability
(full version) |
||||
| 11:50-12:10 |
What is in #P and what is not?
(full version) |
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures
|
Polynomial-Time Power-Sum Decomposition of Polynomials
(full version) |
||||
| 12:15-12:35 |
Quantum Tanner codes
(full version) |
Solving the Hamilton Cycle problem fast on average
(full version) |
NP-Hardness of Learning Programs and Partial MCSP
(full version) |
||||
| 12:35-14:00 | Lunch | ||||||
| Session 10A Colorado A-B |
Session 10B Colorado C-D |
Session 10C Colorado E |
|||||
| 14:00-14:20 |
Online List Labeling: Breaking the log2n Barrier
(full version) |
Indistinguishability Obfuscation via Mathematical Proofs of Equivalence
|
Killing a Vortex
(full version) |
||||
| 14:25-14:45 |
A Hash Table Without Hash Functions, and How to Get the Most out of Your Random Bits
(full version) |
Geometry of Secure Two-party Computation
(full version) |
Low Treewidth Embeddings of Planar and Minor-Free Metrics
(full version) |
||||
| 14:50-15:10 |
Near-Optimal Deterministic Vertex-Failure Connectivity Oracles
(full version) |
Incrementally Verifiable Computation via Rate-1 Batch Arguments
|
An Approximate Generalization of the Okamura-Seymour Theorem
(full version) |
||||
| 15:15-15:35 |
Fast Deterministic Fully Dynamic Distance Approximation
(full version) |
Rate-1 Non-Interactive Arguments for Batch-NP and Applications
|
Shortest Paths without a Map, but with an Entropic Regularizer
(full version) |
||||
| 15:35-16:00 | Break | ||||||
| Session 11A Colorado A-B |
Session 11B Colorado C-D |
Session 11C Colorado E |
|||||
| 16:00-16:20 |
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications
(full version) |
Bounded depth proof for Tseitin formulas on the grid; revisited
(full version) |
Nearly Optimal Communication and Query Complexity of Bipartite Matching
(full version) |
||||
| 16:25-16:45 |
Computing in Anonymous Dynamic Networks Is Linear
(full version) |
Separations in Proof Complexity and TFNP
(full version) |
Strong XOR Lemma for Communication with Bounded Rounds
(full version) |
||||
| 16:50-17:10 |
The Implicit Graph Conjecture is False
(full version) |
Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures
(full version) |
Rounds vs Communication Tradeoffs for Maximal Independent Sets
|
||||
| Conference End | |||||||
Sponsors
 |
 |
 |
 |
 |