IEEE FOCS 2022 Program
All times are in Mountain Standard Time
(floorplan link)
 
Day 1: Monday October 31, 2022
  Session 1A
Colorado A-B (videos)
Session 1B
Colorado C-D (videos)
Session 1C
Colorado E (videos)
09:00-09:20  Binary Codes with Resilience Beyond 1/4 via Interaction
Klim Efremenko, Gillat Kol, Raghuvansh Saxena and Zhijun Zhang
Classical Verification of Quantum Computations in Linear Time
(full version)
Jiayu Zhang
Properly learning monotone functions via local correction
(full version)
Jane Lang, Ronitt Rubinfeld and Arsen Vasilyan
09:25-09:45  Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits
(full version)
Ronen Shaltiel and Jad Silbak
Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography
(full version)
Alexander Meiburg
Testing Positive Semidefiniteness Using Linear Measurements
(full version)
Deanna Needell, William Swartworth and David P. Woodruff
09:50-10:10  Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring
(full version)
Gil Cohen and Tal Yankovitz
Tight Bounds for Quantum State Certification with Incoherent Measurements
(full version)
Sitan Chen, Brice Huang, Jerry Li and Allen Liu
Improved Optimal Testing Results from Global Hypercontractivity
(full version)
Tali Kaufman and Dor Minzer
10:15-10:35  Punctured Low-Bias Codes Behave Like Random Linear Codes
(full version)
Venkatesan Guruswami and Jonathan Mosheiff
Verifiable Quantum Advantage without Structure
(full version)
Takashi Yamakawa and Mark Zhandry
10:35-11:00  Break
11:00-12:30  Workshop A:
Session 1
Colorado A-B (videos)

Advances on Metric Embeddings
Workshop B:
Session 1
Colorado C-D (videos)

New Directions in Derandomization
Workshop C:
Session 1
Colorado E (videos)

Fair Division: Algorithms and Complexity
12:30-14:00  Lunch
  Session 2A
Colorado A-B (videos)
Session 2B
Colorado C-D (videos)
Session 2C
Colorado E (videos)
14:00-14:20  Localization schemes: A framework for proving mixing bounds for Markov chains
(full version)
Yuansi Chen and Ronen Eldan
Pure-Circuit: Strong Inapproximability for PPAD
Argyrios Deligkas, John Fearnley, Alexandros Hollender and Themistoklis Melissourgos
Simple Hard Instances for Low-Depth Algebraic Proofs
(full version)
Nashlen Govindasamy, Tuomas Hakoniemi and Iddo Tzameret
14:25-14:45  Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence
(full version)
Nima Anari, Yang P. Liu and Thuy-Duong Vuong
Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design
(full version)
Bo Peng and Zhihao Gavin Tang
Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits
(full version)
Pranjal Dutta and Nitin Saxena
14:50-15:10  Optimal learning of quantum Hamiltonians from high-temperature Gibbs states
(full version)
Jeongwan Haah, Robin Kothari and Ewin Tang
First Price Auction is 1 - 1 / e2 Efficient
(full version)
Yaonan Jin and Pinyan Lu
Radical Sylvester-Gallai Theorem for Cubics
Rafael Oliveira and Akash Kumar Sengupta
15:15-15:35  Sampling Lovasz Local Lemma For General Constraint Satisfaction Solutions In Near-Linear Time
(full version)
Kun He, Chunyang Wang and Yitong Yin
Fast Multivariate Multipoint Evaluation Over All Finite Fields
(full version)
Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar and Chris Umans
15:35-16:00  Break
16:00-17:30  Workshop A:
Session 2
Colorado A-B (videos)

Advances on Metric Embeddings
Workshop B:
Session 2
Colorado C-D (videos)

New Directions in Derandomization
Workshop C:
Session 2
Colorado E (videos)

Fair Division: Algorithms and Complexity
 
Day 2: Tuesday November 1, 2022
  Session 3A
Colorado A-B (videos)
Session 3B
Colorado C-D (videos)
Session 3C
Colorado E (videos)
09:00-09:20  Solving SDP Faster: A Robust IPM Framework and Efficient Implementation
(full version)
Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao and Ruizhe Zhang
Survivable Network Design Revisited: Group-Connectivity
(full version)
Qingyun Chen, Bundit Laekhanukit, Chao Liao and Yuhao Zhang
Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses
(full version)
Brice Huang and Mark Sellke
09:25-09:45  Improved Lower Bounds for Submodular Function Minimization
(full version)
Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang and Aaron Sidford
Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles
(full version)
Mina Dalirooyfard, Ce Jin, Virginia Vassilevska Williams and Nicole Wein
Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization
(full version)
Ahmed El Alaoui, Andrea Montanari and Mark Sellke
09:50-10:10  Determinant Maximization via Matroid Intersection Algorithms
(full version)
Adam Brown, Aditi Laddha, Madhusudan Pittu, Mohit Singh and Prasad Tetali
Fitting Metrics and Ultrametrics with Minimum Disagreements
(full version)
Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, Arnaud de Mesmay
Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
(full version)
Joao Basso, David Gamarnik, Song Mei and Leo Zhou
10:15-10:35  Interior point methods are not worse than Simplex
(full version)
Xavier Allamigeon, Daniel Dadush, Georg Loho, Bento Natura and László A. Végh
Algorithms for the ferromagnetic Potts model on expanders (full version)
Charlie Carlson, Ewan Davies, Nicolas Fraiman, Alexandra Kolla, Aditya Potukuchi and Corrine Yap
10:35-11:00  Break
11:00-12:30  Workshop A:
Session 3
Colorado A-B (videos)

Advances on Metric Embeddings
Workshop B:
Session 3
Colorado C-D (videos)

New Directions in Derandomization
Workshop D:
Session 1
Colorado E (videos)

Privacy Preserving Machine Learning
12:30-14:00  Lunch
  Plenary Session
Colorado E (videos)
14:00-14:45  Knuth Prize Lecture
Noga Alon
14:50-15:20  On Matrix Multiplication and Polynomial Identity Testing
(full version)
Robert Andrews
15:20-16:00  Break
16:00-17:30  Workshop A:
Session 4
Colorado A-B (videos)

Advances on Metric Embeddings
Workshop B:
Session 4
Colorado C-D (videos)

New Directions in Derandomization
Workshop D:
Session 2
Colorado E (videos)

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 (videos)
Session 4B
Colorado C-D (videos)
Session 4C
Colorado E (videos)
09:00-09:20  Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues
(full version)
Tsz Chiu Kwok, Lap Chi Lau, Kam Chuen Tung
Using invariant theory to fool polynomials
Harm Derksen, Emanuele Viola
Local Computation of Maximal Independent Set
Mohsen Ghaffari
09:25-09:45  Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy and Avi Wigderson
Derandomizing Directed Random Walks in Almost-Linear Time
(full version)
Rasmus Kyng, Simon Meierhans and Maximilian Probst Gutenberg
Streaming Facility Location in High Dimension via Geometric Hashing
(full version)
Artur Czumaj, Shaofeng Jiang, Robert Krauthgamer, Pavel Veselý and Mingwei Yang
09:50-10:10  Motif Cut Sparsifiers
(full version)
Michael Kapralov, Mikhail Makarov, Sandeep Silwal, Christian Sohler and Jakab Tardos
Linear Hashing with ℓ guarantees and two-sided Kakeya bounds
(full version)
Manik Dhar and Zeev Dvir
The Power of Uniform Sampling for Coresets
(full version)
Vladimir Braverman, Vincent Cohen-Addad, Shaofeng Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup and Xuan Wu
10:15-10:35  Unstructured Hardness to Average-Case Randomness
(full version)
Lijie Chen, Ron Rothblum and Roei Tell
On Weighted Graph Sparsification by Linear Sketching
(full version)
Yu Chen, Sanjeev Khanna and Huan Li
10:35-11:00  Break
  Session 5A
Colorado A-B (videos)
Session 5B
Colorado C-D (videos)
Session 5C
Colorado E (videos)
11:00-11:20  Factorial Lower Bounds for (Almost) Random Order Streams
(full version)
Ashish Chiplunkar, John Kallaugher, Michael Kapralov and Eric Price
Induced Cycles and Paths Are Harder Than You Think
(full version)
Mina Dalirrooyfard and Virginia Vassilevska Williams
Sparse random hypergraphs: Non-backtracking spectra and community detection
(full version)
Ludovic Stephan and Yizhe Zhu
11:25-11:45  The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut
(full version)
John Kallaugher and Ojas Parekh
Hardness Self-Amplification from Feasible Hard-Core Sets
(full version)
Shuichi Hirahara and Nobutaka Shimizu
Algorithms and Barriers in the Symmetric Binary Perceptron Model
(full version)
David Gamarnik, Eren Can Kızıldağ, Will Perkins and Changji Xu
11:50-12:10  Cut Query Algorithms with Star Contraction
(full version)
Yuval Efron, Danupon Nanongkai, Sagnik Mukhopadhya, Simon Apers, Troy Lee and Pawel Gawrychowski
A tight (non-combinatorial) conditional lower bound for Klee's Measure Problem in 3D
Marvin Künnemann
Optimal mixing for two-state anti-ferromagnetic spin systems
(full version)
Xiaoyu Chen, Weiming Feng, Yitong Yin and Xinyuan Zhang
12:15-12:35  Memory Bounds for Learning
(full version)
Binghui Peng, Christos Papadimitriou and Xi Chen
12:35-14:00  Lunch
  Session 6 (Plenary)
Colorado E (videos)
14:00-14:30  Negative-Weight Single-Source Shortest Paths in Near-Linear Time
(full version)
Aaron Bernstein, Danupon Nanongkai and Christian Wulff-Nilsen
14:35-15:05  Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
(full version)
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg and Sushant Sachdeva
15:05-16:00  Break
  Session 7A
Colorado A-B (videos)
Session 7B
Colorado C-D (videos)
Session 7C
Colorado E (videos)
16:00-16:20  Randomised Composition and Small-Bias Minimax
(full version)
Shalev Ben-David, Eric Blais, Mika Göös and Gilbert Maystre
Correlation Clustering with Sherali-Adams
(full version)
Vincent Cohen-Addad, Euiwoong Lee and Alantha Newman
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
(full version)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer and Barna Saha
16:25-16:45  A Proof of the Kahn-Kalai Conjecture
(full version)
Huy Tuan Pham and Jinyoung Park
Explicit Lower Bounds Against Ω(n)-Rounds of Sum-of-Squares
(full version)
Max Hopkins and Ting-Chun Lin
Õ(n + poly(k))-time Algorithm for Distance k Tree Edit Distance
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha and Hamed Saleh
16:50-17:10  On the Range Avoidance Problem for Circuits
(full version)
Hanlin Ren, Rahul Santhanam and Zhikun Wang
Faster Pattern Matching under Edit Distance
(full version)
Panagiotis Charalampopoulos, Tomasz Kociumaka and Philip Wellnitz
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 (videos)
Session 8B
Colorado C-D (videos)
Session 8C
Colorado E (videos)
09:00-09:20  Estimating the Longest Increasing Subsequence in Nearly Optimal Time
(full version)
Alexander Andoni, Negev Shekel Nosatzki, Sandip Sinha and Clifford Stein
Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Outdegree Ordering, and Densest Subgraphs
Laxman Dhulipala, Quanquan C. Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun and Shangdi Yu
Balanced Allocations: The Heavily Loaded Case with Deletions
(full version)
Nikhil Bansal and William Kuszmaul
09:25-09:45  Almost 3-Approximate Correlation Clustering in Constant Rounds
(full version)
Soheil Behnezhad, Moses Charikar, Weiyun Ma and Li-Yang Tan
Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets
Shimon Kogan and Merav Parter
Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing
(full version)
Namiko Matsumoto and Arya Mazumdar
09:50-10:10  High-Dimensional Geometric Streaming in Polynomial Space
(full version)
David P. Woodruff and Taisuke Yasuda
New Additive Spanner Lower Bounds by an Unlayered Obstacle Product
(full version)
Greg Bodwin and Gary Hoppenworth
Minimax Rates for Robust Community Detection
(full version)
Allen Liu and Ankur Moitra
10:15-10:35  Active Linear Regression for ℓp Norms and Beyond
(full version)
Cameron Musco, Christopher Musco, David P. Woodruff and Taisuke Yasuda
Deterministic Small Vertex Connectivity in Almost Linear Time
Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP
(full version)
Anna Karlin, Nathan Klein and Shayan Oveis Gharan
10:35-11:00  Break
  Session 9A
Colorado A-B (videos)
Session 9B
Colorado C-D (videos)
Session 9C
Colorado E (videos)
11:00-11:20  Generalised entropy accumulation
(full version)
Tony Metger, Omar Fawzi, David Sutter and Renato Renner
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time
(full version)
Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak and Ohad Trabelsi
Planting Undetectable Backdoors in Machine Learning Models
(full version)
Shafi Goldwasser, Michael P. Kim, Vinod Vaikuntanathan and Or Zamir
11:25-11:45  Post-Quantum Zero Knowledge, Revisited (or: How to Do Quantum Rewinding Undetectably)
(full version)
Alex Lombardi, Fermi Ma and Nicholas Spooner
Constant Approximation of Min-Distances in Near-Linear Time
Shiri Chechik and Tianyi Zhang
A Characterization of Multiclass Learnability
(full version)
Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran and Amir Yehudayoff
11:50-12:10  What is in #P and what is not?
(full version)
Christian Ikenmeyer and Igor Pak
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures
Virginia Vassilevska Williams, Eyob Woldeghebriel and Yinzhan Xu
Polynomial-Time Power-Sum Decomposition of Polynomials
(full version)
Mitali Bafna, Jun-Ting Hsieh, Pravesh Kothari and Jeff Xu
12:15-12:35  Quantum Tanner codes
(full version)
Anthony Leverrier and Gilles Zémor
Solving the Hamilton Cycle problem fast on average
(full version)
Michael Anastos
NP-Hardness of Learning Programs and Partial MCSP
(full version)
Shuichi Hirahara
12:35-14:00  Lunch
  Session 10A
Colorado A-B (videos)
Session 10B
Colorado C-D (videos)
Session 10C
Colorado E (videos)
14:00-14:20  Online List Labeling: Breaking the log2n Barrier
(full version)
Michael A. Bender, Alex Conway, Martin Farach-Colton, Hanna Komlos, William Kuszmaul and Nicole Wein
Indistinguishability Obfuscation via Mathematical Proofs of Equivalence
Abhishek Jain and Zhengzhong Jin
Killing a Vortex
(full version)
Dimitrios Thilikos and Sebastian Wiederrecht
14:25-14:45  A Hash Table Without Hash Functions, and How to Get the Most out of Your Random Bits
(full version)
William Henry Kuszmaul
Geometry of Secure Two-party Computation
(full version)
Saugata Basu, Hamidreza Amini Khorasgani, Hemanta K. Maji and Hai H. Nguyen
Low Treewidth Embeddings of Planar and Minor-Free Metrics
(full version)
Hung Le and Arnold Filtser
14:50-15:10  Near-Optimal Deterministic Vertex-Failure Connectivity Oracles
(full version)
Yaowei Long and Thatchaphol Saranurak
Incrementally Verifiable Computation via Rate-1 Batch Arguments
Omer Paneth and Rafael Pass
An Approximate Generalization of the Okamura-Seymour Theorem
(full version)
Nikhil Kumar
15:15-15:35  Fast Deterministic Fully Dynamic Distance Approximation
(full version)
Jan van den Brand, Sebastian Forster and Yasamin Nazari
Rate-1 Non-Interactive Arguments for Batch-NP and Applications
Lalita Devadas, Rishab Goyal, Yael Tauman Kalai and Vinod Vaikuntanathan
Shortest Paths without a Map, but with an Entropic Regularizer
(full version)
Sebastien Bubeck, Christian Coester and Yuval Rabani
15:35-16:00  Break
  Session 11A
Colorado A-B (videos)
Session 11B
Colorado C-D (videos)
Session 11C
Colorado E (videos)
16:00-16:20  Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications
(full version)
Michael Elkin, Bernhard Haeupler, Václav Rozhoň and Christoph Grunau
Bounded depth proof for Tseitin formulas on the grid; revisited
(full version)
Johan Håstad and Kilian Risse
Nearly Optimal Communication and Query Complexity of Bipartite Matching
(full version)
Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay and Danupon Nanongkai
16:25-16:45  Computing in Anonymous Dynamic Networks Is Linear
(full version)
Giuseppe Antonio Di Luna and Giovanni Viglietta
Separations in Proof Complexity and TFNP
(full version)
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere and Ran Tao
Strong XOR Lemma for Communication with Bounded Rounds
(full version)
Huacheng Yu
16:50-17:10  The Implicit Graph Conjecture is False
(full version)
Hamed Hatami and Pooya Hatami
Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures
(full version)
Aparna Gupte, Neekon Vafa and Vinod Vaikuntanathan
Rounds vs Communication Tradeoffs for Maximal Independent Sets
Sepehr Assadi, Gillat Kol and Zhijun Zhang
Conference End

Sponsors