November 8-11, 2026

New York City, USA

67th IEEE Symposium on Foundations of Computer Science

FOCS 2026 Program

Download program (PDF)Workshop program
Regular talk
15 + 3 min
Award talk
25 + 5 min
Lunch
from 12:50
Track ATrack BTrack CTrack D — Monday onlyPlenary / award

Monday, November 9

4 parallel tracks
9:00 – 9:30 am
Breakfast / Registration
Block 19:30 – 11:00 am

1AFlows, Connectivity and Matchings

9:30 Dynamic Connectivity, Minimum Spanning Tree, and 2-Edge Connectivity with Polylogarithmic Worst-Case Update Time
Simon Meierhans, Maximilian Probst Gutenberg, Yu-Cheng Yeh (ETH Zurich)
9:48 Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth
Yonggang Jiang (MPIINF); Changki Yun (Seoul National University)
10:06 Connectivity augmentation is fixed-parameter tractable
Tuukka Korhonen, Mikkel Thorup (University of Copenhagen)
10:24 Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense Graphs
Bernhard Haeupler (INSAIT, Sofia University "St. Kliment Ohridski" and ETH Zurich); Yonggang Jiang (MPIINF); Thatchaphol Saranurak (University of Michigan)
10:42 A Shortest Augmenting Path Algorithm for Linear Matroid Parity
Kou Hamada, Satoru Iwata (University of Tokyo)

1BQuantum Tomography and Hamiltonian Learning

9:30 Mixed state tomography reduces to pure state tomography
Angelos Pelecanos, Jack Spilecki, Ewin Tang (UC Berkeley); John Wright (The University of California, Berkeley)
9:48 Nearly Time-Optimal Pure State Tomography with Pauli Measurements
Sabee Grewal (UT Austin); Meghal Gupta (UC Berkeley); William He (Carnegie Mellon University); Aniruddha Sen (UT Austin); Mihir Singhal (UC Berkeley)
10:06 Quantum channel tomography: optimal bounds and a Heisenberg-to-classical phase transition
Kean Chen (University of Pennsylvania); Filippo Girardi (Scuola Normale Superiore); Aadil Oufkir (University Mohammed VI Polytechnic); Nengkun Yu (Stony Brook University); Zhicheng Zhang (Griffith University)
10:24 The Keyl--Werner algorithm is not optimal for spectrum estimation
Angelos Pelecanos, Jack Spilecki, Ewin Tang (UC Berkeley); John Wright (The University of California, Berkeley)
10:42 Lower Bounds for Learning Hamiltonians from Time Evolution
Ziyun Chen, Jerry Li, Joe Slote (University of Washington)

1CCryptography

9:30 Doubly-Efficient Interactive Arguments for Bounded-Space from One-Way Functions
Guy Rothblum (Apple)
9:48 Lower Bounds for PIR with Preprocessing from Blackbox Cryptography
Alexander Hoover (Stevens Institute of Technology); Giuseppe Persiano (Università di Salerno); Kevin Yeo (Google)
10:06 On the Hardness of LWE with Trapdoor Hints and Applications to Fuzzy Cryptography
Divesh Aggarwal (National University of Singapore); Aayush Jain (CMU); Huijia (Rachel) Lin (University of Washington); Yuetian Wu (Peking University)
10:24 Overcoming Padding in Cryptography via the Hardness of Certifying Random Strings
Yao-Ching Hsieh (University of Washington); Abhishek Jain (NTT Research and Johns Hopkins); Jiatu Li (Massachusetts Institute of Technology); Surya Mathialagan (NTT Research)
10:42 Undetectable Conversations Between AI Agents via Pseudorandom Noise-Resilient Key Exchange
Vinod Vaikuntanathan (MIT CSAIL); Or Zamir (Tel Aviv University)

1DClustering and Coresets

9:30 A Constant Approximation for Non-Uniform k-Center
Tanmay Inamdar (Indian Institute of Technology Jodhpur); William Lochet (CNRS, LIRMM); Fahad Panolan (School of Computer Science, University of Leeds)
9:48 FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters
Fabrizio Grandoni (IDSIA, USI-SUPSI); Anupam Gupta (New York University, USA); Jatin Yadav (Indian Institute Of Technology, Delhi)
10:06 Fully Dynamic Euclidean k-Means
Sayan Bhattacharya (University of Warwick, UK); Martin Costa, Ermiya Farokhnejad (University of Warwick); Shaofeng Jiang (Peking University); Yaonan Jin (Huawei); Jianing Lou (Peking University)
10:24 k-Clustering via Iterative Randomized Rounding
Jarosław Byrka (University of Wrocław); Yuhao Guo, Yang Hu (Tsinghua University); Shi Li (Nanjing University); Chengzhang Wan (Tsinghua University); Zaixuan Wang (Nanjing University)
10:42 A Polynomial Coreset for Furthest Neighbor in Planar Metrics
Kacper Kluk (University of Warsaw); Hung Le (University of Massachusetts, Amherst, USA); Wojciech Nadara, Marcin Pilipczuk (University of Warsaw); Hector Tierno, Vinayak Vinayak (University of Massachusetts, Amherst)
11:00 – 11:20 am
Coffee Break (20 min)
Block 211:20 am – 12:50 pm

2AShortest Paths and Distances

11:20 Almost Optimal Multiple Source Shortest Paths and Reachability
Barna Saha, Yinzhan Xu, Christopher Ye (University of California, San Diego)
11:38 Bellman-Ford in Almost-Linear Time for Dense Graphs
George Li (Carnegie Mellon University); Jason Li (CMU); Junkai Zhang (Tsinghua University)
11:56 Shortest Paths with Linear Edge Weights
Suryajith Chillara, Kshitij Gajjar (International Institute of Information Technology, Hyderabad); Nithish Raja (Eindhoven University of Technology)
12:14 Distances in Planar Graphs are Almost for Free!
Shay Mozes, Daniel Prigan (Reichman University, Israel)
12:32 Optimal algorithm for 2-Approximate All Pair Shortest Paths --- almost
Manoj Gupta, Mrigankashekhar Shandilya (IIT Gandhinagar)

2BCircuit Lower Bounds and Separations

11:20 A Lower Bound for Non-Commutative Circuits
Ran Raz (Princeton University)
11:38 Exponential lower bounds for depth-3 circuits in small characteristic
Michael A. Forbes (University of Illinois at Urbana-Champaign)
11:56 Derandomized Sunflowers and Radical Lower Bounds
Bruno Cavalar (University of Oxford); Théo Fabris (University of Copenhagen); Partha Mukhopadhyay (Chennai Mathematical Institute); Srikanth Srinivasan, Amir Yehudayoff (University of Copenhagen)
12:14 Near-Maximum Circuit Lower Bounds for Exponential Time with Merlin-Arthur Queries
Hanlin Ren (Institute for Advanced Study); Ryan Williams (MIT)
12:32 Separating RAM and Multitape Turing Machines with Short Random Oracles
Lijie Chen, Yichuan Wang (UC Berkeley)

2CLearning Theory and Calibration

11:20 Robust Learning with Optimal Error
Guy Blanc (Stanford University)
11:38 Robust Learning of Multi-Index Models under Logconcave Distributions via Weak Partial Learners
Ilias Diakonikolas (UW Madison); Daniel M. Kane (University of California, San Diego); Mingchen Ma (UW-Madison)
11:56 Tight Bounds for Learning Polyhedra with a Margin
Shyamal Patel (Columbia University); Santosh Vempala (Georgia Tech)
12:14 Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End
Steve Hanneke (Purdue University); Idan Mehalel (The Hebrew University); Shay Moran (Technion and Google Research)
12:32 Optimal Lower Bounds for Online Multicalibration
Natalie Collina, Jiuyao Lu, Georgy Noarov, Aaron Roth (University of Pennsylvania)

2DGeometry, Polyhedra and Metric Spaces

11:20 A general framework for geometric problems: Low-dimensionality implies a PTAS
Alon Hovav, Yair Bartal (Hebrew University); Lee-Ad Gottlieb (Ariel University)
11:38 L₁-distortion of Earth Mover Distances and Transportation Cost Spaces on High Dimensional Grids
Chris Gartland (UNC Charlotte); Mikhail Ostrovskii (St. John's University); Yuval Rabani (The Hebrew University of Jerusalem); Robert Young (New York University)
11:56 A PTAS for Euclidean Capacitated Vehicle Routing
Zachary Friggstad (University of Alberta); Fabrizio Grandoni, Ramin Mousavi (IDSIA, USI-SUPSI); Kinter Ren, Mohammad R. Salavatipour (University of Alberta)
12:14 Single-Source Shortest Paths and Almost Exact Diameter in Pseudodisk Graphs
Mark de Berg (TU Eindhoven); Bart Jansen (TU Eindhoven, the Netherlands); Jeroen S.K. Lamme (TU Eindhoven)
12:32 Circuit Diameter of Polyhedra is Strongly Polynomial
Bento Natura (Columbia University)
12:50 – 2:20 pm
Lunch (90 minutes)
Block 32:20 – 3:50 pm

3AFine-Grained Complexity

2:20 3SUM Is Really Hard: A Real-to-Integer Reduction
Nick Fischer (Max Planck Institute for Informatics); Adam Polak, Jonas Schmidt (Bocconi University)
2:38 Min-Plus Convolution Lower Bounds via a Higher-Order BSG Theorem
Nick Fischer (Max Planck Institute for Informatics); Ce Jin (UC Berkeley); Yinzhan Xu (University of California, San Diego)
2:56 Dynamic Time Warping in the Low-Distance Regime
Itai Boneh (University of Wrocław); Shay Golan (Ariel University); Tomasz Kociumaka (Max Planck Institute for Informatics)
3:14 Can We Break Fine-Grained and NP-Hardness Barriers if We've Seen the Graph Before? The Isomorphic-Priors Model
Dani Dorfman, Simon Döring, Martin Herold, Danupon Nanongkai (Max Planck Institute for Informatics, Saarland Informatics Campus); Daniel Neuen (TU Dresden); Joachim Spoerhase (University of Liverpool); Zihang Wu (Max Planck Institute for Informatics, Saarland Informatics Campus)
3:32 Pigeonhole Equal Subset Sum: Subexponential Algorithm, Tight Lower Bounds, and Average-Case Analysis
Deepak Bhati (CISPA Helmholtz Center for Information Security); Pranjal Dutta (Nanyang Technological University, Singapore); Antoine Joux, Mahesh Sreekumar Rajasree (CISPA Helmholtz Center for Information Security); Karol Węgrzycki (Max Planck Institute for Informatics)

3BQuantum Circuits and Lower Bounds

2:20 QAC⁰ contains TC⁰ (with many copies of the input)
Daniel Grier, Jackson Morris (University of California, San Diego); Kewen Wu (Institute for Advanced Study)
2:38 Worst-case depth hierarchy for shallow quantum circuits
Min-Hsiu Hsieh, Michael de Oliveira (Hon Hai (Foxconn) Quantum Computing Research Center); Sathyawageeswar Subramanian (University of Oxford); Xingjian Zhang (University of Technology Sydney)
2:56 Quantum Speedups Require Structure or Depth
Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan (Stanford University)
3:14 Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders
Vishnu Iyer, Siddhartha Jain (UT Austin); Stephen Jordan, Rolando D. Somma (Google)
3:32 Tight Quantum Lower Bound for k-Distinctness
Aleksandrs Belovs (University of Latvia)

3CMechanism Design, Fair Division and Fixed Points

2:20 Approximately Efficient Multidimensional Bilateral Trade
Aviad Rubinstein (Stanford University, USA); Xizhi Tan, Zixin Zhou (Stanford University)
2:38 On the Existence of Fair Allocations for Goods and Chores under Dissimilar Preferences
Egor Gagushin, Marios Mertzanidis (Purdue University); Alexandros Psomas (Purdue University and Google Research)
2:56 Sample-efficient black-box reductions in Bayesian mechanism design with independent items
Arya Maheshwari (Carnegie Mellon University); S. Matthew Weinberg, Eric Xue (Princeton University)
3:14 Truthful-in-Expectation Mechanisms for MMS Approximation
Moshe Babaioff (The Hebrew University of Jerusalem); Uriel Feige (Weizmann Institute of Science); Noam Manaker Morag (The Hebrew University of Jerusalem)
3:32 Faster Approximate Fixed Points of ℓ∞-Contractions
Andrei Feodorov, Sebastian Haslebacher (ETH Zurich)

3DStreaming, Sketching and Communication

2:20 Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streams
Elena Gribelyuk (Princeton University); Honghao Lin, David P. Woodruff (Carnegie Mellon University); Huacheng Yu (Princeton University); Samson Zhou (Texas A&M University)
2:38 Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
Cheng Jiang (MIT); Yinchen Liu (Tsinghua University); Huacheng Yu (Princeton University)
Merged · one talk slot
2:56 Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
Noah G. Singer (Carnegie Mellon University); Madhur Tulsiani (Toyota Technological Institute at Chicago); Santhoshini Velusamy (University of Waterloo)
Near-Optimal Space Lower Bounds for Streaming CSPs
Yumou Fei, Dor Minzer, Shuo Wang (MIT)
3:14 Quality control in sublinear time: a case study via random graphs
Cassandra Marcussen (Harvard University); Ronitt Rubinfeld (MIT); Madhu Sudan (Harvard University)
3:32 Short and Sweet: Computationally Efficient Collaborative Communication Through Indistinguishability and Coarsening
Mark Bedaywi, Scott Emmons, Nika Haghtalab, Stuart Russell (UC Berkeley)
3:50 – 4:10 pm
Coffee Break (20 min)
Block 44:10 – 5:58 pm

4AData Structures and Space–Time Tradeoffs

4:10 An Ω((log n / log log n)²) Cell-Probe Lower Bound for Dynamic Boolean Data Structures
Young Kun Ko (Pennsylvania State University)
4:28 Compressed Inverse Suffix Arrays
Sharma V. Thankachan (North Carolina State University)
4:46 Dynamic Entropy-Encoded Arrays in O(1) Time with Nearly Optimal Space
Guy E. Blelloch (Carnegie Mellon University); Yang Hu (Tsinghua University); William Kuszmaul (Carnegie Mellon University); Tianxiao Li (Independent Researcher); Renfei Zhou (Carnegie Mellon University)
5:04 Sorting under Partial Information with Optimal Preprocessing Time via Unified Bound Heaps
Daniel Rutschmann (Institute of Science and Technology Austria (ISTA))
Merged · one talk slot
5:22 Improved space-time tradeoff for TSP via extremal set systems
Justin Dallant, László Kozma (Dresden University of Technology)
Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
Afrouz Jabal Ameli, Jesper Nederlof, Shengzhe Wang (Utrecht University)
5:40 The Power of Two-Choice Linear Probing
Amir Azarmehr (Northeastern University); Michael Bender (Stony Brook University); William Kuszmaul, Rose Silver (Carnegie Mellon University)

4BProof Complexity and Space-Bounded Computation

4:10 Hard CNF Instances for Ideal Proof Systems: The ROABP Case
Tuomas Hakoniemi (University of Helsinki); Nutan Limaye (IT University of Copenhagen); Iddo Tzameret (Imperial College London)
4:28 Many Proof Complexity Generators Inside One Demi-Bits Generator
Xin Li (Johns Hopkins University); Hanlin Ren (Institute for Advanced Study); Yan Zhong (Johns Hopkins University)
4:46 Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
Susanna F. de Rezende, David Engström (Lund University); Yassine Ghannane (University of Copenhagen); Kilian Risse (Lund University)
5:04 The Proof Analysis Problem for Constant-Depth Frege
Noel Arteche (Lund University & University of Copenhagen); Susanna de Rezende (Lund University); Erfan Khaniki (University of Oxford); Kilian Risse (Lund University)
5:22 Limit on the computational power of C-random strings
Alexey Milovanov (University of Lisbon)
5:40 Composing Low-Space Algorithms
Edward Pyne (MIT); Roei Tell (University of Toronto)

4COnline Algorithms, Scheduling and Optimization

4:10 Online Algorithms via Minimax and Posterior Matching
Thomas Kesselheim (University of Bonn); Marco Molinaro (Microsoft Research); Kalen Patton, Sahil Singla (Georgia Institute of Technology)
4:28 Optimal Online Bin Packing under Prophet, Random-Order, and Learning-from-Samples Models
Kailash Gopal Darmasubramanian (Indian Institute of Technology, Madras); Samyak Jha, Arindam Khan, K. V. N. Sreenivas (Indian Institute of Science, Bengaluru)
4:46 The Instability of all Backoff Protocols
Leslie Ann Goldberg (University of Oxford); John Lapinskas (University of Bristol)
5:04 Breaking the Barrier of 2 for Approximating Weighted Throughput Maximization via the Sherali-Adams Hierarchy
Alexander Armbruster (Technical University of Munich); Fabrizio Grandoni (IDSIA, USI-SUPSI); Andreas Wiese (Technical University of Munich)
5:22 NP-Hardness and a PTAS for the Pinwheel Problem
Robert Kleinberg, Ahan Mishra (Cornell University)
5:40 Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory
Michael Menart (University of Toronto, Vector Institute); Sasho Nikolov (University of Toronto); Ohad Shamir (Weizmann Institute and University of Toronto)

4DParameterized Algorithms and Enumeration

4:10 Branch-width of connectivity functions is fixed-parameter tractable
Tuukka Korhonen (University of Copenhagen); Sang-il Oum (Institute for Basic Science)
4:28 Fixed-Parameter Tractability and Hardness for Steiner Rooted and Locally Connected Orientations
Kristóf Bérczi (Eötvös Loránd University); Florian Hörsch (CISPA Helmholtz Center for Information Security); András Imolay (Eötvös Loránd University); Tamás Schwarcz (London School of Economics and Political Science)
4:46 Optimal Bounds for the k-Disjoint Paths Problem
Maximilian Gorsky (Institute for Basic Science); Dario Giuliano Cavallaro, Stephan Kreutzer (TU Berlin); Dimitrios Thilikos (LIRMM, Univ Montpellier, CNRS, Montpellier, France); Sebastian Wiederrecht (KAIST)
5:04 Weighted Treewidth on Minor-Free Graphs: Combinatorics and Approximation
Dániel Marx (CISPA Helmholtz Center for Information Security); Michał Pilipczuk (University of Warsaw, Poland); Karol Węgrzycki (Max Planck Institute for Informatics)
5:22 Efficiently Listing Projected Trees, and Equivalence of Listing and Enumeration
Karl Bringmann (ETH Zurich); Nick Fischer (Max Planck Institute for Informatics); Yanheng Wang (ETH Zürich)
6:30 – 7:45 pm
Business Meeting

Tuesday, November 10

3 parallel tracks; afternoon given to the award sessions
9:00 – 9:30 am
Breakfast
Block 59:30 – 11:00 am

5AQuantum Information Theory

9:30 Constructive counterexamples to the additivity of minimum output Rényi entropy of quantum channels for all p > 1
Harm Derksen (Northeastern University); Benjamin Lovitz (Concordia University)
9:48 On the undecidability of quantum channel capacities
Archishna Bhattacharyya, Arthur Mehta (University of Ottawa); Yuming Zhao (University of Copenhagen)
10:06 A quasipolynomial-time classical algorithm for SYK thermal expectations
Alexander Zlokapa (MIT)
10:24 DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians
Zhengfeng Ji (Tsinghua University); Tongyang Li (Peking University); Changpeng Shao (Academy of Mathematics and System Sciences, Chinese Academy of Sciences); Xinzhao Wang (Peking University); Yuxin Zhang (Academy of Mathematics and Systems Science, Chinese Academy of Sciences)
10:42 Explicit Separations for One-Query Unitary Synthesis
Fangqi Dong, Alex Lombardi (Princeton University); Fermi Ma (New York University)

5BQuantum Cryptography and Oracles

9:30 Classical Obfuscation of Quantum Circuits via Publicly-Verifiable QFHE
James Bartusek (Columbia); Aparna Gupte (MIT CSAIL); Saachi Mutreja (Columbia); Omri Shmueli (NTT Research)
9:48 Obfuscation of Arbitrary Quantum Circuits (via Subspace-Preserving Pseudorandom Unitary)
Er-Cheng Tang (University of Washington); Mi-Ying Miryam Huang (University of Southern California)
10:06 Certified Randomness without Structure Against Shallow-Query Adversaries
Dakshita Khurana (UIUC and NTT Research); Bhaskar Roberts, Avishay Tal (UC Berkeley)
10:24 Quantum oracles, weak and strong
John Wright (The University of California, Berkeley); Ewin Tang (UC Berkeley); Mark Zhandry (Stanford)
10:42 Separating Quantum and Classical Advice with Good Codes
Andrew Huang (MIT); John Bostanci (Columbia University); Vinod Vaikuntanathan (MIT)

5CCoding Theory and Error Correction

9:30 Efficient and rate-optimal list-decoding in the presence of minimal feedback: Weldon and Slepian-Wolf in sheep's clothing
Pranav Joshi (California Institute of Technology); Daniel McMorrow (National University of Singapore); Yihan Zhang (University of Bristol); Amitalok J. Budkuley (Indian Institute of Technology Kharagpur); Sidharth Jaggi (University of Bristol)
9:48 Towards a Unified Algorithmic Framework for Shannon's Theorem
Sayan Bhattacharya (University of Warwick, UK); Martin Costa (University of Warwick); Shay Solomon (Tel Aviv University); Tianyi Zhang (Nanjing University)
10:06 Linear-Time Encodable and Decodable Quantum Error-Correcting Codes
Adam Wills (Center for Theoretical Physics --- a Leinweber Institute, Massachusetts Institute of Technology, Cambridge, MA; Hon Hai (Foxconn) Research Institute, Taipei, Taiwan); Ting-Chun Lin (Department of Physics, University of California at San Diego, La Jolla, CA; Hon Hai (Foxconn) Research Institute, Taipei, Taiwan); Rachel Yun Zhang (CSAIL, Massachusetts Institute of Technology, Cambridge, MA); Min-Hsiu Hsieh (Hon Hai (Foxconn) Research Institute, Taipei, Taiwan)
10:24 Explicit Constant-Alphabet Subspace Design Codes
Rohan Goyal (MIT); Venkatesan Guruswami (UC Berkeley); Jun-Ting Hsieh (Massachusetts Institute of Technology)
10:42 Error-Correction of Matrix Multiplication Algorithms over Integers
Shuichi Hirahara (National Institute of Informatics); Nobutaka Shimizu (Institute of Science Tokyo)
11:00 – 11:20 am
Coffee Break (20 min)
Block 611:20 am – 12:50 pm

6ASampling and Counting

11:20 A computational phase transition for learning-to-sample from Ising models
Andrej Risteski (Carnegie Mellon University); Thuy-Duong (June) Vuong (UC San Diego)
11:38 Rapid mixing in positively weighted restricted Boltzmann machines
Weiming Feng (The University of Hong Kong); Heng Guo (University of Edinburgh); Minji Yang (The University of Hong Kong)
11:56 Subquadratic Counting via Perfect Marginal Sampling
Xiaoyu Chen (MIT); Zongchen Chen (Georgia Institute of Technology); Kuikui Liu (MIT); Xinyuan Zhang (Nanjing University)
12:14 Non-existence probabilities and lower tails in the critical regime via Belief Propagation
Matthew Jenssen (King's College London); Will Perkins (Georgia Institute of Technology); Aditya Potukuchi (Max Planck Institute for Software Systems); Michael Simkin (MIT)
12:32 On Sampling Lower Bounds for Polynomials
Mohammad Mahdi Khodabandeh, Igor Shinkar (Simon Fraser University)

6BRandom Structures and Constraint Satisfaction

11:20 Strong Low Degree Hardness for Stable Local Optima in Spin Glasses
Brice Huang (Stanford); Mark Sellke (Harvard)
11:38 Stable algorithms cannot reliably find isolated perceptron solutions
Shuyang Gong (Peking University); Brice Huang (Stanford University); Shuangping Li (Yale University); Mark Sellke (Harvard University)
11:56 Sharp Lovasz-Theta Bounds on Random Graphs
Aaron Potechin (University of Chicago); Jeff Xu (TTIC)
12:14 Expanders Meet Reed--Muller: Easy Instances of Noisy k-XOR
Jarosław Błasiok, Paul Lou, Alon Rosen (Bocconi University); Madhu Sudan (Harvard University)
12:32 The Richness of CSP Non-redundancy
Joshua Brakensiek (University of California, Berkeley); Venkatesan Guruswami (UC Berkeley); Bart Jansen (TU Eindhoven, the Netherlands); Victor Lagerkvist (Linköpings universitet); Magnus Wahlstrom (Royal Holloway, University of London, UK)

6CCommunication, Space-Bounded and Algebraic Algorithms

11:20 Gap-Majority Lemmas in Communication Complexity
Pachara Sawettamalya, Huacheng Yu (Princeton University)
11:38 No Constant-Cost Protocol for Point–Line Incidence
Mika Göös (EPFL); Nathaniel Harms (UBC); Florian K. Richter, Anastasia Sofronova (EPFL)
11:56 Space-Efficient Simulations Beyond Multitape Turing Machines
Danil Sibgatullin, Ryan Williams (MIT)
12:14 Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2
Joshua A. Grochow (University of Colorado—Boulder); Gabor Ivanyos (Hungarian Academy of Sciences); Youming Qiao (University of New South Wales); Xiaorui Sun (University of Illinois Chicago)
12:32 Approximating the Permanent of a Random Matrix with Polynomially Small Mean: Zeros and Universality
Frederic Koehler, Pui Kuen Leung (University of Chicago)
12:50 – 2:35 pm
Lunch (1 hour 45 minutes)
Plenary2:35 – 4:05 pm

Best Paper Session

single track · 3 × 30 min (25 + 5 for questions)

2:35 Rational degree is polynomially related to degreeRobin Kothari (Google); Matt Kovacs-Deak (University of Maryland); Daochen Wang, Rain Zimin Yang (University of British Columbia)
3:05 Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis ConjectureStephen Arndt, Benjamin Moseley (Carnegie Mellon University); Kirk Pruhs (University of Pittsburgh); Chaitanya Swamy (University of Waterloo); Michael Zlatin (Pomona College)
3:35 The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time ColoringYuta Inoue (The University of Tokyo); Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo); Atsuyuki Miyashita (The University of Tokyo); Bojan Mohar (Simon Fraser University, Burnaby, Canada); Carsten Thomassen (Technical University of Denmark); Mikkel Thorup (University of Copenhagen)
4:05 – 4:30 pm
Coffee Break (25 min)
Plenary4:30 – 5:30 pm

Best Student Paper Session

single track · 2 × 30 min (25 + 5 for questions)

4:30 Flip Distance Between Triangulations of Convex Polygons is NP-CompleteJoseph Dorfer (Graz University of Technology)
5:00 Parity ∉ QAC⁰ ⇔ QAC⁰ is Fourier-ConcentratedLucas Gretta, Meghal Gupta, Malvika Raj Joshi (UC Berkeley)
7:30 – 10:00 pm
Joint FOCS + TCC Reception — Eisner, NYU (room turnover 5:30 – 7:30)

Wednesday, November 11

3 parallel tracks, with the Knuth Prize Lecture after lunch
9:00 – 9:30 am
Breakfast
Block 79:30 – 11:00 am

7AAlgebraic Complexity and Tensors

9:30 Schur complements for tensors and multilinear commutative rank
Guy Moshkovitz (City University of New York); Daniel G. Zhu (Princeton University)
9:48 The edge of the asymptotic spectrum of tensors
Josh Alman, Baitian Li, Kevin Pratt (Columbia University)
10:06 Strassen's support functionals coincide with the quantum functionals: a general classical-quantum correspondence for optimization on entanglement polytopes and beyond
Keiya Sakabe, Mahmut Levent Doğan, Michael Walter (LMU Munich)
10:24 Hilbert's Nullstellensatz is in the Counting Hierarchy
Robert Andrews, Abhibhav Garg, Éric Schost (University of Waterloo)
10:42 A Unifying Framework for Quasi-Polynomial Optimization of Fixed-degree Polynomials
Martino Bernasconi (Bocconi Univeristy); Matteo Castiglioni (Politecnico di Milano); Andrea Celli (Bocconi University); Gabriele Farina (MIT)

7BPCPs and Hardness of Approximation

9:30 Direct-product testers and PCPs from coset complexes
Ryan O'Donnell, Noah G. Singer (Carnegie Mellon University)
9:48 Classical Adversarial Fault-Tolerance and PCPs
Anurag Anshu (Harvard University); Nikolas Breuckmann (University of Bristol); Louis Golowich (UC Berkeley); Quynh T Nguyen (Harvard University); Umesh Vazirani (UC Berkeley)
10:06 Gap Amplification for Local Hamiltonians with Combinatorial Soundness
Mitali Bafna (University of Washington); Quynh T Nguyen (Harvard University); Tina Zhang (MIT)
10:24 Deterministic Hardness of Approximation for SVP in all Finite ℓₚ Norms
Isaac Hair (UCSB, UCLA); Amit Sahai (UCLA)
10:42 Optimal PSPACE-hardness of Approximating q-CSP Reconfiguration
Shuichi Hirahara (National Institute of Informatics); Naoto Ohsaka (CyberAgent, Inc.)

7CConstraint Satisfaction and Boolean Functions

9:30 Conservative Maltsev Constraint Satisfaction Problems
Andrew Moorhead, Manuel Bodirsky (TU Dresden)
9:48 Singleton algorithms for the Constraint Satisfaction Problem
Dmitriy Zhuk (Charles University, Prague)
10:06 Approximate polymorphisms of predicates
Yuval Filmus, Yaroslav Alekseev (Technion)
10:24 PTF Lower Bounds from Low-Degree Testing Lower Bounds in Additive Noise Models
Ilias Diakonikolas (UW Madison); Daniel M. Kane (University of California, San Diego); Sihan Liu (UCSD); Trung Tran (University of California, San Diego)
10:42 DNF formulas are efficiently testable with relative error
William Pires (Columbia); Xi Chen, Toniann Pitassi, Rocco A. Servedio (Columbia University)
11:00 – 11:20 am
Coffee Break (20 min)
Block 811:20 am – 12:50 pm

8ACodes, Fault Tolerance and Information

11:20 Recovering Polynomials over Finite Fields from Noisy Character Values
Swastik Kopparty (University of Toronto)
11:38 Explicit Almost-Optimal ε-Balanced Codes via Free Expander Walks
Jun-Ting Hsieh (Massachusetts Institute of Technology); Sidhanth Mohanty (Northwestern University); Rachel Yun Zhang (MIT)
11:56 Explicit Rank Extractors and Subspace Designs via Function Fields, with Applications to Strong Blocking Sets
Zeyu Guo, Roshan Raj (The Ohio State University); Chong Shangguan (Shandong University); Zihan Zhang (The Ohio State University)
12:14 Fault-Tolerant Quantum Computation with Adversarial Errors
Nikolas Breuckmann (University of Bristol); Louis Golowich, Umesh Vazirani (UC Berkeley)
12:32 Zero-error information equals amortized communication complexity
Daiki Suruga (CFT PAN)

8BStructural Graph Theory

11:20 Polynomial χ-boundedness for excluding P₅
Tung Nguyen (University of Oxford)
11:38 Hereditary 2-WQO Graph Classes Have Bounded Clique-Width
Julien Duron, Nikolas Mählmann, Szymon Toruńczyk (University of Warsaw)
11:56 The Lovász conjecture holds for moderately dense Cayley graphs
Benjamin Bedert (Univeversity of Cambridge); Nemanja Draganic, Alp Muyesser (University of Oxford); Matias Pavez-Signe (University of Chile)
12:14 A coarse Menger's Theorem for planar graphs
Václav Blažej, Michał Pilipczuk, Evangelos Protopapas (Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland)
12:32 Better Bounds For Graph Reconstruction
Antoni Buraczewski, Paweł Gawrychowski (University of Wrocław)

8CEquilibria, Welfare and Price of Anarchy

11:20 On the Complexity of Learning Nash Equilibria
Oliver Biggar (Columbia University); Christos Papadimitriou (Columbia U); Georgios Piliouras (Google DeepMind / SUTD)
11:38 The Complexity of Computing a Unique Nash Equilibrium
Abheek Ghosh (Technical University of Munich); Paul W. Goldberg, Alexandros Hollender (University of Oxford)
11:56 The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
Xi Chen, Yuhao Li, Mihalis Yannakakis (Columbia University)
12:14 The Price of Anarchy for Selfish Load Balancing
Xihan Deng (Shanghai Jiao Tong University); Yaonan Jin (Hong Kong University of Science and Technology); Wenqian Wang, Yuhao Zhang (Shanghai Jiao Tong University)
12:32 Online Submodular Welfare Maximization: Computation is not the Bottleneck
Rajan Udwani (UC Berkeley); David Wajc (Technion)
12:50 – 2:20 pm
Lunch (90 minutes)
Plenary2:20 – 3:35 pm

Knuth Prize Lecture

single track · 75 min

3:35 – 4:00 pm
Coffee Break (25 min)
Block 94:00 – 5:12 pm

9AGraph Algorithms and Distance Oracles

4:00 Vertex-Failure Distance Oracles and Labeling Schemes: Compact and Constant-Approximate
Yaowei Long (University of Michigan)
4:18 A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
Kuowen Chen (Tsinghua University); Nicole Wein (University of Michigan, Ann Arbor, USA); Yiran Zhang (Tsinghua University)
4:36 Approximate Spanning Tree Counting from Uncorrelated Edge Sets
Yang Liu, Richard Peng, Junzhao Yang (Carnegie Mellon University)
4:54 Instance-Optimality of Bidirectional PageRank Estimation
Mikkel Thorup (University of Copenhagen); Hanzhi Wang (The University of Melbourne)

9BSublinear Algorithms and Property Testing

4:00 Õ(1)-Depth Parallel Reachability Faster than Transitive Closure
Shimon Kogan, Merav Parter (Weizmann)
4:18 Graph k-Coloring in Sublinear Average Time
Cassandra Marcussen (Harvard University); Edward Pyne, Ronitt Rubinfeld (MIT); Asaf Shapira, Shlomo Tauber (Tel Aviv University)
4:36 Testing Properties of Edge Distributions
Yumou Fei (MIT)
4:54 Efficient and Private Property Testing via Indistinguishability
Cynthia Dwork, Pranay Tankala (Harvard University)

9CPrivacy and Learning

4:00 Local Node Differential Privacy
Sofya Raskhodnikova, Adam Smith, Connor Wagaman, Anatoly Zavyalov (Boston University)
4:18 The Sample Complexity of Membership Inference and Privacy Auditing
Mahdi Haghifam (TTIC); Adam Smith (Boston University); Jonathan Ullman (Northeastern University)
4:36 The optimal information complexity of VC learning
Steve Hanneke, Juexiao Wang (Purdue University)
4:54 Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery
Chao Gao (University of Chicago); Liren Shan (Toyota Technological Institute at Chicago); Vaidehi Srinivas, Aravindan Vijayaraghavan (Northwestern University)
5:12 – 5:32 pm
Coffee Break (20 min)
Block 105:32 – 6:44 pm

10AApproximation and Exact Algorithms

5:32 An O(log log n)-Approximation Algorithm for Submodular Unsplittable Flow on a Path
Alexander Armbruster (Technical University of Munich); Fabrizio Grandoni (IDSIA, USI-SUPSI); Andreas Wiese (Technical University of Munich); Ruilong Zhang (City University of Hong Kong (Dongguan))
5:50 Stochastic Gradient Meets Randomized Rounding: New Algorithms for Node-Weighted Steiner Problems
Joseph Koutsoutis, Jesse Lerner, Roie Levin, Jiawei Yu (Rutgers University)
6:08 Improved Upper Bounds for the Directed Flow-Cut Gap
Greg Bodwin, Luba Samborska (University of Michigan)
6:26 Dense Subset Sum in Multi-Dimension
Lin Chen, Tingwei Hu, Yuchen Mao, Guochuan Zhang (Zhejiang University)

10BOptimization, Refutation and Parameterized Approximation

5:32 Strongly Refuting Random CSP without Literals
Siu On Chan (Unaffiliated); Tommaso D'Orsi (Bocconi University); Jeff Xu (TTIC)
5:50 Fast Convergence of Gradient Descent on Random ℓₚ-Norm Regression
Yang Liu, Richard Peng, Weina Wang, Junzhao Yang (Carnegie Mellon University)
6:08 A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition
Ioannis Anagnostides (Carnegie Mellon University); Gabriele Farina (MIT); Tuomas Sandholm (Carnegie Mellon University); Brian Hu Zhang (MIT)
6:26 Optimal FPT-Approximability for Modular Linear Equations
Konrad K. Dabrowski (Newcastle University); Peter Jonsson (Linköping University); Sebastian Ordyniak (University of Leeds, UK); George Osipov (University of Oxford); Magnus Wahlstrom (Royal Holloway, University of London, UK)

10CHashing, Contention and Communication

5:32 Fast Insertion for Bucketized Cuckoo Hashing
Tolson Bell, William Kuszmaul (Carnegie Mellon University)
5:50 Online Graph Balancing and the Power of Two Choices
Nikhil Bansal, Milind Prabhu (University of Michigan); Sahil Singla (Georgia Institute of Technology); Siddharth Meenachi Sundaram (Georgia Tech)
6:08 The communication complexity of distributed estimation
Parikshit Gopalan (Apple); Raghu Meka (UCLA); Prasad Raghavendra, Mihir Singhal (UC Berkeley); Avi Wigderson (Institute for Advanced Study)
6:26 Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication
Guangxu Yang, Jiapeng Zhang (University of Southern California)