{"id":1653,"date":"2026-03-06T18:27:45","date_gmt":"2026-03-06T18:27:45","guid":{"rendered":"https:\/\/focs.computer.org\/2026\/accepted-papers\/"},"modified":"2026-07-20T18:49:13","modified_gmt":"2026-07-20T18:49:13","slug":"accepted-papers","status":"publish","type":"page","link":"https:\/\/focs.computer.org\/2026\/accepted-papers\/","title":{"rendered":"Accepted Papers"},"content":{"rendered":"\t\t
\n\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

FOCS 2026 Accepted Papers<\/strong><\/h2>\n\n
\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
$\\tilde{O}(1)$-Depth Parallel Reachability Faster than Transitive Closure<\/span>Shimon Kogan, Merav Parter (Weizmann)<\/span><\/td>\n<\/tr>\n
$L_1$-distortion of Earth Mover Distances and Transportation Cost Spaces on High Dimensional Grids<\/span>Chris Gartland (UNC Charlotte); Mikhail Ostrovskii (St. John’s University); Yuval Rabani (The Hebrew University of Jerusalem); Robert Young (New York University)<\/span><\/td>\n<\/tr>\n
3SUM Is Really Hard: A Real-to-Integer Reduction<\/span>Nick Fischer (Max Planck Institute for Informatics); Adam Polak, Jonas Schmidt (Bocconi University)<\/span><\/td>\n<\/tr>\n
A coarse Menger’s Theorem for planar graphs<\/span>V\u00e1clav Bla\u017eej, Micha\u0142 Pilipczuk, Evangelos Protopapas (Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland)<\/span><\/td>\n<\/tr>\n
A computational phase transition for learning-to-sample from Ising models<\/span>Andrej Risteski (Carnegie Mellon University); Thuy-Duong (June) Vuong (UC San Diego)<\/span><\/td>\n<\/tr>\n
A Constant Approximation for Non-Uniform k-Center<\/span>Tanmay Inamdar (Indian Institute of Technology Jodhpur); William Lochet (CNRS, LIRMM); Fahad Panolan (School of Computer Science, University of Leeds)<\/span><\/td>\n<\/tr>\n
A general framework for geometric problems: Low-dimensionality implies a PTAS<\/span>Alon Hovav, Yair Bartal (Hebrew University); Lee-Ad Gottlieb (Ariel University)<\/span><\/td>\n<\/tr>\n
A Lower Bound for Non-Commutative Circuits<\/span>Ran Raz (Princeton University)<\/span><\/td>\n<\/tr>\n
A Polynomial Coreset for Furthest Neighbor in Planar Metrics<\/span>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)<\/span><\/td>\n<\/tr>\n
A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs<\/span>Kuowen Chen (Tsinghua University); Nicole Wein (University of Michigan, Ann Arbor, USA); Yiran Zhang (Tsinghua University)<\/span><\/td>\n<\/tr>\n
A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition<\/span>Ioannis Anagnostides (Carnegie Mellon University); Gabriele Farina (MIT); Tuomas Sandholm (Carnegie Mellon University); Brian Hu Zhang (MIT)<\/span><\/td>\n<\/tr>\n
A PTAS for Euclidean Capacitated Vehicle Routing<\/span>Zachary Friggstad (University of Alberta); Fabrizio Grandoni, Ramin Mousavi (IDSIA, USI-SUPSI); Kinter Ren, Mohammad R. Salavatipour (University of Alberta)<\/span><\/td>\n<\/tr>\n
A quasipolynomial-time classical algorithm for SYK thermal expectations<\/span>Alexander Zlokapa (MIT)<\/span><\/td>\n<\/tr>\n
A Shortest Augmenting Path Algorithm for Linear Matroid Parity<\/span>Kou Hamada, Satoru Iwata (University of Tokyo)<\/span><\/td>\n<\/tr>\n
A Unifying Framework for Quasi-Polynomial Optimization of Fixed-degree Polynomials<\/span>Martino Bernasconi (Bocconi Univeristy); Matteo Castiglioni (Politecnico di Milano); Andrea Celli (Bocconi University); Gabriele Farina (MIT)<\/span><\/td>\n<\/tr>\n
Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streams<\/span>Elena Gribelyuk (Princeton University); Honghao Lin, David P. Woodruff (Carnegie Mellon University); Huacheng Yu (Princeton University); Samson Zhou (Texas A&M University)<\/span><\/td>\n<\/tr>\n
Almost Optimal Multiple Source Shortest Paths and Reachability<\/span>Barna Saha, Yinzhan Xu, Christopher Ye (University of California, San Diego)<\/span><\/td>\n<\/tr>\n
An $\\Omega ( (\\log n \/ \\log \\log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures<\/span>Young Kun Ko (Pennsylvania State University)<\/span><\/td>\n<\/tr>\n
An O(log log n)-Approximation Algorithm for Submodular Unsplittable Flow on a Path<\/span>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))<\/span><\/td>\n<\/tr>\n
Approximate polymorphisms of predicates<\/span>Yuval Filmus, Yaroslav Alekseev (Technion)<\/span><\/td>\n<\/tr>\n
Approximate Spanning Tree Counting from Uncorrelated Edge Sets<\/span>Yang Liu, Richard Peng, Junzhao Yang (Carnegie Mellon University)<\/span><\/td>\n<\/tr>\n
Approximately Efficient Multidimensional Bilateral Trade<\/span>Aviad Rubinstein (Stanford University, USA); Xizhi Tan, Zixin Zhou (Stanford University)<\/span><\/td>\n<\/tr>\n
Approximating the Permanent of a Random Matrix with Polynomially Small Mean: Zeros and Universality<\/span>Frederic Koehler, Pui Kuen Leung (University of Chicago)<\/span><\/td>\n<\/tr>\n
Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota’s Basis Conjecture<\/span>Stephen Arndt, Benjamin Moseley (Carnegie Mellon University); Kirk Pruhs (University of Pittsburgh); Chaitanya Swamy (University of Waterloo); Michael Zlatin (Pomona College)<\/span><\/td>\n<\/tr>\n
Bellman-Ford in Almost-Linear Time for Dense Graphs<\/span>George Li (Carnegie Mellon University); Jason Li (CMU); Junkai Zhang (Tsinghua University)<\/span><\/td>\n<\/tr>\n
Better Bounds For Graph Reconstruction<\/span>Antoni Buraczewski, Pawe\u0142 Gawrychowski (University of Wroc\u0142aw)<\/span><\/td>\n<\/tr>\n
Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2<\/span>Joshua A. Grochow (University of Colorado\u2014Boulder); Gabor Ivanyos (Hungarian Academy of Sciences); Youming Qiao (University of New South Wales); Xiaorui Sun (University of Illinois Chicago)<\/span><\/td>\n<\/tr>\n
Branch-width of connectivity functions is fixed-parameter tractable<\/span>Tuukka Korhonen (University of Copenhagen); Sang-il Oum (Institute for Basic Science)<\/span><\/td>\n<\/tr>\n
Breaking the Barrier of 2 for Approximating Weighted Throughput Maximization via the Sherali-Adams Hierarchy<\/span>Alexander Armbruster (Technical University of Munich); Fabrizio Grandoni (IDSIA, USI-SUPSI); Andreas Wiese (Technical University of Munich)<\/span><\/td>\n<\/tr>\n
Can We Break Fine-Grained and NP-Hardness Barriers if We’ve Seen the Graph Before? The Isomorphic-Priors Model<\/span>Dani Dorfman, Simon D\u00f6ring, 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)<\/span><\/td>\n<\/tr>\n
Certified Randomness without Structure Against Shallow-Query Adversaries<\/span>Dakshita Khurana (UIUC and NTT Research); Bhaskar Roberts, Avishay Tal (UC Berkeley)<\/span><\/td>\n<\/tr>\n
Circuit Diameter of Polyhedra is Strongly Polynomial<\/span>Bento Natura (Columbia University)<\/span><\/td>\n<\/tr>\n
Classical Adversarial Fault-Tolerance and PCPs<\/span>Anurag Anshu (Harvard University); Nikolas Breuckmann (University of Bristol); Louis Golowich (UC Berkeley); Quynh T Nguyen (Harvard University); Umesh Vazirani (UC Berkeley)<\/span><\/td>\n<\/tr>\n
Classical Obfuscation of Quantum Circuits via Publicly-Verifiable QFHE<\/span>James Bartusek (Columbia); Aparna Gupte (MIT CSAIL); Saachi Mutreja (Columbia); Omri Shmueli (NTT Research)<\/span><\/td>\n<\/tr>\n
Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense Graphs<\/span>Bernhard Haeupler (INSAIT, Sofia University “St. Kliment Ohridski” and ETH Zurich); Yonggang Jiang (MPIINF); Thatchaphol Saranurak (University of Michigan)<\/span><\/td>\n<\/tr>\n
Composing Low-Space Algorithms<\/span>Edward Pyne (MIT); Roei Tell (University of Toronto)<\/span><\/td>\n<\/tr>\n
Compressed Inverse Suffix Arrays<\/span>Sharma V. Thankachan (North Carolina State University)<\/span><\/td>\n<\/tr>\n
Connectivity augmentation is fixed-parameter tractable<\/span>Tuukka Korhonen, Mikkel Thorup (University of Copenhagen)<\/span><\/td>\n<\/tr>\n
Conservative Maltsev Constraint Satisfaction Problems<\/span>Andrew Moorhead, Manuel Bodirsky (TU Dresden)<\/span><\/td>\n<\/tr>\n
Constructive counterexamples to the additivity of minimum output R\u00e9nyi entropy of quantum channels for all p > 1<\/span>Harm Derksen (Northeastern University); Benjamin Lovitz (Concordia University)<\/span><\/td>\n<\/tr>\n
Dense Subset Sum in Multi-Dimension<\/span>Lin Chen, Tingwei Hu, Yuchen Mao, Guochuan Zhang (Zhejiang University)<\/span><\/td>\n<\/tr>\n
Derandomized Sunflowers and Radical Lower Bounds<\/span>Bruno Cavalar (University of Oxford); Th\u00e9o Fabris (University of Copenhagen); Partha Mukhopadhyay (Chennai Mathematical Institute); Srikanth Srinivasan, Amir Yehudayoff (University of Copenhagen)<\/span><\/td>\n<\/tr>\n
Deterministic Hardness of Approximation For SVP in all Finite $\\ell_p$ Norms<\/span>Isaac Hair (UCSB, UCLA); Amit Sahai (UCLA)<\/span><\/td>\n<\/tr>\n
Direct-product testers and PCPs from coset complexes<\/span>Ryan O’Donnell, Noah G. Singer (Carnegie Mellon University)<\/span><\/td>\n<\/tr>\n
Distances in Planar Graphs are Almost for Free!<\/span>Shay Mozes, Daniel Prigan (Reichman University, Israel)<\/span><\/td>\n<\/tr>\n
DNF formulas are efficiently testable with relative error<\/span>William Pires (Columbia); Xi Chen, Toniann Pitassi, Rocco A. Servedio (Columbia University)<\/span><\/td>\n<\/tr>\n
Doubly-Efficient Interactive Arguments for Bounded-Space from One-Way Functions<\/span>Guy Rothblum (Apple)<\/span><\/td>\n<\/tr>\n
DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians<\/span>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)<\/span><\/td>\n<\/tr>\n
Dynamic Connectivity, Minimum Spanning Tree, and 2-Edge Connectivity with Polylogarithmic Worst-Case Update Time<\/span>Simon Meierhans, Maximilian Probst Gutenberg, Yu-Cheng Yeh (ETH Zurich)<\/span><\/td>\n<\/tr>\n
Dynamic Entropy-Encoded Arrays in O(1) Time with Nearly Optimal Space<\/span>Guy E. Blelloch (Carnegie Mellon University); Yang Hu (Tsinghua University); William Kuszmaul (Carnegie Mellon University); Tianxiao Li (Independent Researcher); Renfei Zhou (Carnegie Mellon University)<\/span><\/td>\n<\/tr>\n
Dynamic Time Warping in the Low-Distance Regime<\/span>Itai Boneh (University of Wroc\u0142aw); Shay Golan (Ariel University); Tomasz Kociumaka (Max Planck Institute for Informatics)<\/span><\/td>\n<\/tr>\n
Efficient and Private Property Testing via Indistinguishability<\/span>Cynthia Dwork, Pranay Tankala (Harvard University)<\/span><\/td>\n<\/tr>\n
Efficient and rate-optimal list-decoding in the presence of minimal feedback: Weldon and Slepian-Wolf in sheep’s clothing<\/span>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)<\/span><\/td>\n<\/tr>\n
Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders<\/span>Vishnu Iyer, Siddhartha Jain (UT Austin); Stephen Jordan, Rolando D. Somma (Google)<\/span><\/td>\n<\/tr>\n
Efficiently Listing Projected Trees, and Equivalence of Listing and Enumeration<\/span>Karl Bringmann (ETH Zurich); Nick Fischer (Max Planck Institute for Informatics); Yanheng Wang (ETH Z\u00fcrich)<\/span><\/td>\n<\/tr>\n
Error-Correction of Matrix Multiplication Algorithms over Integers<\/span>Shuichi Hirahara (National Institute of Informatics); Nobutaka Shimizu (Institute of Science Tokyo)<\/span><\/td>\n<\/tr>\n
Expanders Meet Reed–Muller: Easy Instances of Noisy k-XOR<\/span>Jaros\u0142aw B\u0142asiok, Paul Lou, Alon Rosen (Bocconi University); Madhu Sudan (Harvard University)<\/span><\/td>\n<\/tr>\n
Explicit Almost-Optimal \u03b5-Balanced Codes via Free Expander Walks<\/span>Jun-Ting Hsieh (Massachusetts Institute of Technology); Sidhanth Mohanty (Northwestern University); Rachel Yun Zhang (MIT)<\/span><\/td>\n<\/tr>\n
Explicit Constant-Alphabet Subspace Design Codes<\/span>Rohan Goyal (MIT); Venkatesan Guruswami (UC Berkeley); Jun-Ting Hsieh (Massachusetts Institute of Technology)<\/span><\/td>\n<\/tr>\n
Explicit Rank Extractors and Subspace Designs via Function Fields, with Applications to Strong Blocking Sets<\/span>Zeyu Guo, Roshan Raj (The Ohio State University); Chong Shangguan (Shandong University); Zihan Zhang (The Ohio State University)<\/span><\/td>\n<\/tr>\n
Explicit Separations for One-Query Unitary Synthesis<\/span>Fangqi Dong, Alex Lombardi (Princeton University); Fermi Ma (New York University)<\/span><\/td>\n<\/tr>\n
Exponential lower bounds for depth-3 circuits in small characteristic<\/span>Michael A. Forbes (University of Illinois at Urbana-Champaign)<\/span><\/td>\n<\/tr>\n
Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication<\/span>Guangxu Yang, Jiapeng Zhang (University of Southern California)<\/span><\/td>\n<\/tr>\n
Fast Convergene of Gradient Descent on Random $\\ell_{p}$-Norm Regression<\/span>Yang Liu, Richard Peng, Weina Wang, Junzhao Yang (Carnegie Mellon University)<\/span><\/td>\n<\/tr>\n
Fast Insertion for Bucketized Cuckoo Hashing<\/span>Tolson Bell, William Kuszmaul (Carnegie Mellon University)<\/span><\/td>\n<\/tr>\n
Faster Approximate Fixed Points of $\\ell_\\infty$-Contractions<\/span>Andrei Feodorov, Sebastian Haslebacher (ETH Zurich)<\/span><\/td>\n<\/tr>\n
Fault-Tolerant Quantum Computation with Adversarial Errors<\/span>Nikolas Breuckmann (University of Bristol); Louis Golowich, Umesh Vazirani (UC Berkeley)<\/span><\/td>\n<\/tr>\n
Fixed-Parameter Tractability and Hardness for Steiner Rooted and Locally Connected Orientations<\/span>Krist\u00f3f B\u00e9rczi (E\u00f6tv\u00f6s Lor\u00e1nd University); Florian H\u00f6rsch (CISPA Helmholtz Center for Information Security); Andr\u00e1s Imolay (E\u00f6tv\u00f6s Lor\u00e1nd University); Tam\u00e1s Schwarcz (London School of Economics and Political Science)<\/span><\/td>\n<\/tr>\n
Flip Distance Between Triangulations of Convex Polygons is NP-Complete<\/span>Joseph Dorfer (Graz University of Technology)<\/span><\/td>\n<\/tr>\n
FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters<\/span>Fabrizio Grandoni (IDSIA, USI-SUPSI); Anupam Gupta (New York University, USA); Jatin Yadav (Indian Institute Of Technology, Delhi)<\/span><\/td>\n<\/tr>\n
Fully Dynamic Euclidean k-Means<\/span>Sayan Bhattacharya (University of Warwick, UK); Martin Costa, Ermiya Farokhnejad (University of Warwick); Shaofeng Jiang (Peking University); Yaonan Jin (Huawei); Jianing Lou (Peking University)<\/span><\/td>\n<\/tr>\n
Gap Amplification for Local Hamiltonians with Combinatorial Soundness<\/span>Mitali Bafna (University of Washington); Quynh T Nguyen (Harvard University); Tina Zhang (MIT)<\/span><\/td>\n<\/tr>\n
Gap-Majority Lemmas in Communication Complexity<\/span>Pachara Sawettamalya, Huacheng Yu (Princeton University)<\/span><\/td>\n<\/tr>\n
Graph k-Coloring in Sublinear Average Time<\/span>Cassandra Marcussen (Harvard University); Edward Pyne, Ronitt Rubinfeld (MIT); Asaf Shapira, Shlomo Tauber (Tel Aviv University)<\/span><\/td>\n<\/tr>\n
Hard CNF Instances for Ideal Proof Systems: The ROABP Case<\/span>Tuomas Hakoniemi (University of Helsinki); Nutan Limaye (IT University of Copenhagen); Iddo Tzameret (Imperial College London)<\/span><\/td>\n<\/tr>\n
Hereditary 2-WQO Graph Classes Have Bounded Clique-Width<\/span>Julien Duron, Nikolas M\u00e4hlmann, Szymon Toru\u0144czyk (University of Warsaw)<\/span><\/td>\n<\/tr>\n
Hilbert’s Nullstellensatz is in the Counting Hierarchy<\/span>Robert Andrews, Abhibhav Garg, \u00c9ric Schost (University of Waterloo)<\/span><\/td>\n<\/tr>\n
Improved space-time tradeoff for TSP via extremal set systems<\/span>Justin Dallant, L\u00e1szl\u00f3 Kozma (Dresden University of Technology)<\/span><\/td>\n<\/tr>\n
Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics<\/span>Afrouz Jabal Ameli, Jesper Nederlof, Shengzhe Wang (Utrecht University)<\/span><\/td>\n<\/tr>\n
Improved Upper Bounds for the Directed Flow-Cut Gap<\/span>Greg Bodwin, Luba Samborska (University of Michigan)<\/span><\/td>\n<\/tr>\n
Instance-Optimality of Bidirectional PageRank Estimation<\/span>Mikkel Thorup (University of Copenhagen); Hanzhi Wang (The University of Melbourne)<\/span><\/td>\n<\/tr>\n
k-Clustering via Iterative Randomized Rounding<\/span>Jaros\u0142aw Byrka (University of Wroc\u0142aw); Yuhao Guo, Yang Hu (Tsinghua University); Shi Li (Nanjing University); Chengzhang Wan (Tsinghua University); Zaixuan Wang (Nanjing University)<\/span><\/td>\n<\/tr>\n
Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery<\/span>Chao Gao (University of Chicago); Liren Shan (Toyota Technological Institute at Chicago); Vaidehi Srinivas, Aravindan Vijayaraghavan (Northwestern University)<\/span><\/td>\n<\/tr>\n
Limit on the computational power of C-random strings<\/span>Alexey Milovanov (University of Lisbon)<\/span><\/td>\n<\/tr>\n
Linear-Time Encodable and Decodable Quantum Error-Correcting Codes<\/span>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)<\/span><\/td>\n<\/tr>\n
Local Node Differential Privacy<\/span>Sofya Raskhodnikova, Adam Smith, Connor Wagaman, Anatoly Zavyalov (Boston University)<\/span><\/td>\n<\/tr>\n
Lower Bounds for Learning Hamiltonians from Time Evolution<\/span>Ziyun Chen, Jerry Li, Joe Slote (University of Washington)<\/span><\/td>\n<\/tr>\n
Lower Bounds for PIR with Preprocessing from Blackbox Cryptography<\/span>Alexander Hoover (Stevens Institute of Technology); Giuseppe Persiano (Universit\u00e0 di Salerno); Kevin Yeo (Google)<\/span><\/td>\n<\/tr>\n
Many Proof Complexity Generators Inside One Demi-Bits Generator<\/span>Xin Li (Johns Hopkins University); Hanlin Ren (Institute for Advanced Study); Yan Zhong (Johns Hopkins University)<\/span><\/td>\n<\/tr>\n
Min-Plus Convolution Lower Bounds via a Higher-Order BSG Theorem<\/span>Nick Fischer (Max Planck Institute for Informatics); Ce Jin (UC Berkeley); Yinzhan Xu (University of California, San Diego)<\/span><\/td>\n<\/tr>\n
Mixed state tomography reduces to pure state tomography<\/span>Angelos Pelecanos, Jack Spilecki, Ewin Tang (UC Berkeley); John Wright (The University of California, Berkeley)<\/span><\/td>\n<\/tr>\n
Near-Maximum Circuit Lower Bounds for Exponential Time with Merlin-Arthur Queries<\/span>Hanlin Ren (Institute for Advanced Study); Ryan Williams (MIT)<\/span><\/td>\n<\/tr>\n
Near-Optimal Space Lower Bounds for Streaming CSPs<\/span>Yumou Fei, Dor Minzer, Shuo Wang (MIT)<\/span><\/td>\n<\/tr>\n
Nearly Time-Optimal Pure State Tomography with Pauli Measurements<\/span>Sabee Grewal (UT Austin); Meghal Gupta (UC Berkeley); William He (Carnegie Mellon University); Aniruddha Sen (UT Austin); Mihir Singhal (UC Berkeley)<\/span><\/td>\n<\/tr>\n
No Constant-Cost Protocol for Point\u2013Line Incidence<\/span>Mika G\u00f6\u00f6s (EPFL); Nathaniel Harms (UBC); Florian K. Richter, Anastasia Sofronova (EPFL)<\/span><\/td>\n<\/tr>\n
Non-existence probabilities and lower tails in the critical regime via Belief Propagation<\/span>Matthew Jenssen (King’s College London); Will Perkins (Georgia Institute of Technology); Aditya Potukuchi (Max Planck Institute for Software Systems); Michael Simkin (MIT)<\/span><\/td>\n<\/tr>\n
NP-Hardness and a PTAS for the Pinwheel Problem<\/span>Robert Kleinberg, Ahan Mishra (Cornell University)<\/span><\/td>\n<\/tr>\n
Obfuscation of Arbitrary Quantum Circuits (via Subspace-Preserving Pseudorandom Unitary)<\/span>Er-Cheng Tang (University of Washington); Mi-Ying Miryam Huang (University of Southern California)<\/span><\/td>\n<\/tr>\n
On Sampling Lower Bounds for Polynomials<\/span>Mohammad Mahdi Khodabandeh, Igor Shinkar (Simon Fraser University)<\/span><\/td>\n<\/tr>\n
On the Complexity of Learning Nash Equilibria<\/span>Oliver Biggar (Columbia University); Christos Papadimitriou (Columbia U); Georgios Piliouras (Google DeepMind \/ SUTD)<\/span><\/td>\n<\/tr>\n
On the Existence of Fair Allocations for Goods and Chores under Dissimilar Preferences<\/span>Egor Gagushin, Marios Mertzanidis (Purdue University); Alexandros Psomas (Purdue University and Google Research)<\/span><\/td>\n<\/tr>\n
On the Hardness of LWE with Trapdoor Hints and Applications to Fuzzy Cryptography<\/span>Divesh Aggarwal (National University of Singapore); Aayush Jain (CMU); Huijia (Rachel) Lin (University of Washington); Yuetian Wu (Peking University)<\/span><\/td>\n<\/tr>\n
On the undecidability of quantum channel capacities<\/span>Archishna Bhattacharyya, Arthur Mehta (University of Ottawa); Yuming Zhao (University of Copenhagen)<\/span><\/td>\n<\/tr>\n
Online Algorithms via Minimax and Posterior Matching<\/span>Thomas Kesselheim (University of Bonn); Marco Molinaro (Microsoft Research); Kalen Patton, Sahil Singla (Georgia Institute of Technology)<\/span><\/td>\n<\/tr>\n
Online Graph Balancing and the Power of Two Choices<\/span>Nikhil Bansal, Milind Prabhu (University of Michigan); Sahil Singla (Georgia Institute of Technology); Siddharth Meenachi Sundaram (Georgia Tech)<\/span><\/td>\n<\/tr>\n
Online Submodular Welfare Maximization: Computation is not the Bottleneck<\/span>Rajan Udwani (UC Berkeley); David Wajc (Technion)<\/span><\/td>\n<\/tr>\n
Optimal algorithm for 2-Approximate All Pair Shortest Paths — almost<\/span>Manoj Gupta, Mrigankashekhar Shandilya (IIT Gandhinagar)<\/span><\/td>\n<\/tr>\n
Optimal Bounds for the k-Disjoint Paths Problem<\/span>Maximilian Gorsky (Institute for Basic Science); Dario Giuliano Cavallaro, Stephan Kreutzer (TU Berlin); Dimitrios Thilikos (LIRMM, Univ Montpellier, CNRS, Montpellier, France); Sebastian Wiederrecht (KAIST)<\/span><\/td>\n<\/tr>\n
Optimal FPT-Approximability for Modular Linear Equations<\/span>Konrad K. Dabrowski (Newcastle University); Peter Jonsson (Link\u00f6ping University); Sebastian Ordyniak (University of Leeds, UK); George Osipov (University of Oxford); Magnus Wahlstrom (Royal Holloway, University of London, UK)<\/span><\/td>\n<\/tr>\n
Optimal Lower Bounds for Online Multicalibration<\/span>Natalie Collina, Jiuyao Lu, Georgy Noarov, Aaron Roth (University of Pennsylvania)<\/span><\/td>\n<\/tr>\n
Optimal Online Bin Packing under Prophet, Random-Order, and Learning-from-Samples Models<\/span>Kailash Gopal Darmasubramanian (Indian Institute of Technology, Madras); Samyak Jha, Arindam Khan, K. V. N. Sreenivas (Indian Institute of Science, Bengaluru)<\/span><\/td>\n<\/tr>\n
Optimal PSPACE-hardness of Approximating $q$-CSP Reconfiguration<\/span>Shuichi Hirahara (National Institute of Informatics); Naoto Ohsaka (CyberAgent, Inc.)<\/span><\/td>\n<\/tr>\n
Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs<\/span>Noah G. Singer (Carnegie Mellon University); Madhur Tulsiani (Toyota Technological Institute at Chicago); Santhoshini Velusamy (University of Waterloo)<\/span><\/td>\n<\/tr>\n
Overcoming Padding in Cryptography via the Hardness of Certifying Random Strings<\/span>Yao-Ching Hsieh (University of Washington); Abhishek Jain (NTT Research and Johns Hopkins); Jiatu Li (Massachusetts Institute of Technology); Surya Mathialagan (NTT Research)<\/span><\/td>\n<\/tr>\n
Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth<\/span>Yonggang Jiang (MPIINF); Changki Yun (Seoul National University)<\/span><\/td>\n<\/tr>\n
Parity \u2209 QAC\u2070 \u21d4 QAC\u2070 is Fourier-Concentrated<\/span>Lucas Gretta, Meghal Gupta, Malvika Raj Joshi (UC Berkeley)<\/span><\/td>\n<\/tr>\n
Pigeonhole Equal Subset Sum: Subexponential Algorithm, Tight Lower Bounds, and Average-Case Analysis<\/span>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\u0119grzycki (Max Planck Institute for Informatics)<\/span><\/td>\n<\/tr>\n
Polynomial $\\chi$-boundedness for excluding $P_5$<\/span>Tung Nguyen (University of Oxford)<\/span><\/td>\n<\/tr>\n
PTF Lower Bounds from Low-Degree Testing Lower Bounds in Additive Noise Models<\/span>Ilias Diakonikolas (UW Madison); Daniel M. Kane (University of California, San Diego); Sihan Liu (UCSD); Trung Tran (University of California, San Diego)<\/span><\/td>\n<\/tr>\n
QAC^0 contains TC^0 (with many copies of the input)<\/span>Daniel Grier, Jackson Morris (University of California, San Diego); Kewen Wu (Institute for Advanced Study)<\/span><\/td>\n<\/tr>\n
Quality control in sublinear time: a case study via random graphs<\/span>Cassandra Marcussen (Harvard University); Ronitt Rubinfeld (MIT); Madhu Sudan (Harvard University)<\/span><\/td>\n<\/tr>\n
Quantum channel tomography: optimal bounds and a Heisenberg-to-classical phase transition<\/span>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)<\/span><\/td>\n<\/tr>\n
Quantum oracles, weak and strong<\/span>John Wright (The University of California, Berkeley); Ewin Tang (UC Berkeley); Mark Zhandry (Stanford)<\/span><\/td>\n<\/tr>\n
Quantum Speedups Require Structure or Depth<\/span>Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan (Stanford University)<\/span><\/td>\n<\/tr>\n
Rapid mixing in positively weighted restricted Boltzmann machines<\/span>Weiming Feng (The University of Hong Kong); Heng Guo (University of Edinburgh); Minji Yang (The University of Hong Kong)<\/span><\/td>\n<\/tr>\n
Rational degree is polynomially related to degree<\/span>Robin Kothari (Google); Matt Kovacs-Deak (University of Maryland); Daochen Wang, Rain Zimin Yang (University of British Columbia)<\/span><\/td>\n<\/tr>\n
Recovering Polynomials over Finite Fields from Noisy Character Values<\/span>Swastik Kopparty (University of Toronto)<\/span><\/td>\n<\/tr>\n
Robust Learning of Multi-Index Models under Logconcave Distributions via Weak Partial Learners<\/span>Ilias Diakonikolas (UW Madison); Daniel M. Kane (University of California, San Diego); Mingchen Ma (UW-Madison)<\/span><\/td>\n<\/tr>\n
Robust Learning with Optimal Error<\/span>Guy Blanc (Stanford University)<\/span><\/td>\n<\/tr>\n
Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End<\/span>Steve Hanneke (Purdue University); Idan Mehalel (The Hebrew University); Shay Moran (Technion and Google Research)<\/span><\/td>\n<\/tr>\n
Sample-efficient black-box reductions in Bayesian mechanism design with independent items<\/span>Arya Maheshwari (Carnegie Mellon University); S. Matthew Weinberg, Eric Xue (Princeton University)<\/span><\/td>\n<\/tr>\n
Schur complements for tensors and multilinear commutative rank<\/span>Guy Moshkovitz (City University of New York); Daniel G. Zhu (Princeton University)<\/span><\/td>\n<\/tr>\n
Separating Quantum and Classical Advice with Good Codes<\/span>Andrew Huang (MIT); John Bostanci (Columbia University); Vinod Vaikuntanathan (MIT)<\/span><\/td>\n<\/tr>\n
Separating RAM and Multitape Turing Machines with Short Random Oracles<\/span>Lijie Chen, Yichuan Wang (UC Berkeley)<\/span><\/td>\n<\/tr>\n
Sharp Lovasz-Theta Bounds on Random Graphs<\/span>Aaron Potechin (University of Chicago); Jeff Xu (TTIC)<\/span><\/td>\n<\/tr>\n
Short and Sweet: Computationally Efficient Collaborative Communication Through Indistinguishability and Coarsening<\/span>Mark Bedaywi, Scott Emmons, Nika Haghtalab, Stuart Russell (UC Berkeley)<\/span><\/td>\n<\/tr>\n
Shortest Paths with Linear Edge Weights<\/span>Suryajith Chillara, Kshitij Gajjar (International Institute of Information Technology, Hyderabad); Nithish Raja (Eindhoven University of Technology)<\/span><\/td>\n<\/tr>\n
Single-Source Shortest Paths and Almost Exact Diameter in Pseudodisk Graphs<\/span>Mark de Berg (TU Eindhoven); Bart Jansen (TU Eindhoven, the Netherlands); Jeroen S.K. Lamme (TU Eindhoven)<\/span><\/td>\n<\/tr>\n
Singleton algorithms for the Constraint Satisfaction Problem<\/span>Dmitriy Zhuk (Charles University, Prague)<\/span><\/td>\n<\/tr>\n
Sorting under Partial Information with Optimal Preprocessing Time via Unified Bound Heaps<\/span>Daniel Rutschmann (Institute of Science and Technology Austria (ISTA))<\/span><\/td>\n<\/tr>\n
Space-Efficient Simulations Beyond Multitape Turing Machines<\/span>Danil Sibgatullin, Ryan Williams (MIT)<\/span><\/td>\n<\/tr>\n
Stable algorithms cannot reliably find isolated perceptron solutions<\/span>Shuyang Gong (Peking University); Brice Huang (Stanford University); Shuangping Li (Yale University); Mark Sellke (Harvard University)<\/span><\/td>\n<\/tr>\n
Stochastic Gradient Meets Randomized Rounding: New Algorithms for Node-Weighted Steiner Problems<\/span>Joseph Koutsoutis, Jesse Lerner, Roie Levin, Jiawei Yu (Rutgers University)<\/span><\/td>\n<\/tr>\n
Strassen’s support functionals coincide with the quantum functionals: a general classical-quantum correspondence for optimization on entanglement polytopes and beyond<\/span>Keiya Sakabe, Mahmut Levent Do\u011fan, Michael Walter (LMU Munich)<\/span><\/td>\n<\/tr>\n
Strong Low Degree Hardness for Stable Local Optima in Spin Glasses<\/span>Brice Huang (Stanford); Mark Sellke (Harvard)<\/span><\/td>\n<\/tr>\n
Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory<\/span>Michael Menart (University of Toronto, Vector Institute); Sasho Nikolov (University of Toronto); Ohad Shamir (Weizmann Institute and University of Toronto)<\/span><\/td>\n<\/tr>\n
Strongly Refuting Random CSP without Literals<\/span>Siu On Chan (Unaffiliated); Tommaso D’Orsi (Bocconi University); Jeff Xu (TTIC)<\/span><\/td>\n<\/tr>\n
Subquadratic Counting via Perfect Marginal Sampling<\/span>Xiaoyu Chen (MIT); Zongchen Chen (Georgia Institute of Technology); Kuikui Liu (MIT); Xinyuan Zhang (Nanjing University)<\/span><\/td>\n<\/tr>\n
Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size<\/span>Susanna F. de Rezende, David Engstr\u00f6m (Lund University); Yassine Ghannane (University of Copenhagen); Kilian Risse (Lund University)<\/span><\/td>\n<\/tr>\n
Testing Properties of Edge Distributions<\/span>Yumou Fei (MIT)<\/span><\/td>\n<\/tr>\n
The communication complexity of distributed estimation<\/span>Parikshit Gopalan (Apple); Raghu Meka (UCLA); Prasad Raghavendra, Mihir Singhal (UC Berkeley); Avi Wigderson (Institute for Advanced Study)<\/span><\/td>\n<\/tr>\n
The Complexity of Computing a Unique Nash Equilibrium<\/span>Abheek Ghosh (Technical University of Munich); Paul W. Goldberg, Alexandros Hollender (University of Oxford)<\/span><\/td>\n<\/tr>\n
The edge of the asymptotic spectrum of tensors<\/span>Josh Alman, Baitian Li, Kevin Pratt (Columbia University)<\/span><\/td>\n<\/tr>\n
The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring<\/span>Yuta 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)<\/span><\/td>\n<\/tr>\n
The Instability of all Backoff Protocols<\/span>Leslie Ann Goldberg (University of Oxford); John Lapinskas (University of Bristol)<\/span><\/td>\n<\/tr>\n
The Keyl–Werner algorithm is not optimal for spectrum estimation<\/span>Angelos Pelecanos, Jack Spilecki, Ewin Tang (UC Berkeley); John Wright (The University of California, Berkeley)<\/span><\/td>\n<\/tr>\n
The Lov\\’asz conjecture holds for moderately dense Cayley graphs<\/span>Benjamin Bedert (Univeversity of Cambridge); Nemanja Draganic, Alp Muyesser (University of Oxford); Matias Pavez-Signe (University of Chile)<\/span><\/td>\n<\/tr>\n
The Mystery Deepens: On the Query Complexity of Tarski Fixed Points<\/span>Xi Chen, Yuhao Li, Mihalis Yannakakis (Columbia University)<\/span><\/td>\n<\/tr>\n
The optimal information complexity of VC learning<\/span>Steve Hanneke, Juexiao Wang (Purdue University)<\/span><\/td>\n<\/tr>\n
The Power of Two-Choice Linear Probing<\/span>Amir Azarmehr (Northeastern University); Michael Bender (Stony Brook University); William Kuszmaul, Rose Silver (Carnegie Mellon University)<\/span><\/td>\n<\/tr>\n
The Price of Anarchy for Selfish Load Balancing<\/span>Xihan Deng (Shanghai Jiao Tong University); Yaonan Jin (Hong Kong University of Science and Technology); Wenqian Wang, Yuhao Zhang (Shanghai Jiao Tong University)<\/span><\/td>\n<\/tr>\n
The Proof Analysis Problem for Constant-Depth Frege<\/span>Noel Arteche (Lund University & University of Copenhagen); Susanna de Rezende (Lund University); Erfan Khaniki (University of Oxford); Kilian Risse (Lund University)<\/span><\/td>\n<\/tr>\n
The Richness of CSP Non-redundancy<\/span>Joshua Brakensiek (University of California, Berkeley); Venkatesan Guruswami (UC Berkeley); Bart Jansen (TU Eindhoven, the Netherlands); Victor Lagerkvist (Link\u00f6pings universitet); Magnus Wahlstrom (Royal Holloway, University of London, UK)<\/span><\/td>\n<\/tr>\n
The Sample Complexity of Membership Inference and Privacy Auditing<\/span>Mahdi Haghifam (TTIC); Adam Smith (Boston University); Jonathan Ullman (Northeastern University)<\/span><\/td>\n<\/tr>\n
Tight Bounds for Learning Polyhedra with a Margin<\/span>Shyamal Patel (Columbia University); Santosh Vempala (Georgia Tech)<\/span><\/td>\n<\/tr>\n
Tight Quantum Lower Bound for k-Distinctness<\/span>Aleksandrs Belovs (University of Latvia)<\/span><\/td>\n<\/tr>\n
Towards a Unified Algorithmic Framework for Shannon’s Theorem<\/span>Sayan Bhattacharya (University of Warwick, UK); Martin Costa (University of Warwick); Shay Solomon (Tel Aviv University); Tianyi Zhang (Nanjing University)<\/span><\/td>\n<\/tr>\n
Truthful-in-Expectation Mechanisms for MMS Approximation<\/span>Moshe Babaioff (The Hebrew University of Jerusalem); Uriel Feige (Weizmann Institute of Science); Noam Manaker Morag (The Hebrew University of Jerusalem)<\/span><\/td>\n<\/tr>\n
Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams<\/span>Cheng Jiang (MIT); Yinchen Liu (Tsinghua University); Huacheng Yu (Princeton University)<\/span><\/td>\n<\/tr>\n
Undetectable Conversations Between AI Agents via Pseudorandom Noise-Resilient Key Exchange<\/span>Vinod Vaikuntanathan (MIT CSAIL); Or Zamir (Tel Aviv University)<\/span><\/td>\n<\/tr>\n
Vertex-Failure Distance Oracles and Labeling Schemes: Compact and Constant-Approximate<\/span>Yaowei Long (University of Michigan)<\/span><\/td>\n<\/tr>\n
Weighted Treewidth on Minor-Free Graphs: Combinatorics and Approximation<\/span>D\u00e1niel Marx (CISPA Helmholtz Center for Information Security); Micha\u0142 Pilipczuk (University of Warsaw, Poland); Karol W\u0119grzycki (Max Planck Institute for Informatics)<\/span><\/td>\n<\/tr>\n
Worst-case depth hierarchy for shallow quantum circuits<\/span>Min-Hsiu Hsieh, Michael de Oliveira (Hon Hai (Foxconn) Quantum Computing Research Center); Sathyawageeswar Subramanian (University of Oxford); Xingjian Zhang (University of Technology Sydney)<\/span><\/td>\n<\/tr>\n
Zero-error information equals amortized communication complexity<\/span>Daiki Suruga (CFT PAN)<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"

FOCS 2026 Accepted Papers $tilde{O}(1)$-Depth Parallel Reachability Faster than Transitive ClosureShimon Kogan, Merav Parter (Weizmann) $L_1$-distortion of Earth Mover Distances and Transportation Cost Spaces on High Dimensional GridsChris Gartland (UNC Charlotte); Mikhail Ostrovskii (St. John’s University); Yuval Rabani (The Hebrew University of Jerusalem); Robert Young (New York University) 3SUM Is Really Hard: A Real-to-Integer ReductionNick […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":"","_members_access_role":[],"_members_access_error":""},"class_list":["post-1653","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/focs.computer.org\/2026\/wp-json\/wp\/v2\/pages\/1653","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/focs.computer.org\/2026\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/focs.computer.org\/2026\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/focs.computer.org\/2026\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/focs.computer.org\/2026\/wp-json\/wp\/v2\/comments?post=1653"}],"version-history":[{"count":9,"href":"https:\/\/focs.computer.org\/2026\/wp-json\/wp\/v2\/pages\/1653\/revisions"}],"predecessor-version":[{"id":1746,"href":"https:\/\/focs.computer.org\/2026\/wp-json\/wp\/v2\/pages\/1653\/revisions\/1746"}],"wp:attachment":[{"href":"https:\/\/focs.computer.org\/2026\/wp-json\/wp\/v2\/media?parent=1653"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}