{"id":82,"date":"2025-01-31T19:43:36","date_gmt":"2025-01-31T19:43:36","guid":{"rendered":"https:\/\/focs.computer.org\/2025\/accepted-papers\/"},"modified":"2025-10-25T03:01:00","modified_gmt":"2025-10-25T03:01:00","slug":"accepted-papers","status":"publish","type":"page","link":"https:\/\/focs.computer.org\/2025\/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 2025 Accepted Papers<\/strong><\/h2>

(The paper order has been randomized.)<\/em><\/p>\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

\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

The Power of Recursive Embeddings for $\\ell_p$ Metrics <\/em>
Robert Krauthgamer, Nir Petruschka, Shay Sapir (Weizmann Institute)<\/p><\/td><\/tr>

Group Order is in QCMA <\/em>
Fran\u00e7ois Le Gall, Harumichi Nishimura, Dhara Thakkar (Nagoya University)<\/p><\/td><\/tr>

Maximally Extendable Product Codes are Good Coboundary Expanders <\/em>
Gleb Kalachev, Pavel Panteleev (Moscow State University)<\/p><\/td><\/tr>

Obfuscation of Unitary Quantum Programs <\/em>
Mi-Ying Huang (University of Southern California), Er-Cheng Tang (University of Washington)<\/p><\/td><\/tr>

Solving Linear Inequalities over Convex Sets & its Applications to Cryptography and Hydrodynamics <\/em>
Saugata Basu, Hamidreza Amini Khorasgani, Hemanta K. Maji (Purdue University), Hai H. Nguyen (ETH Zurich)<\/p><\/td><\/tr>

Godel in Cryptography: Effectively Zero Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness <\/em>
Rahul Ilango (Massachusetts Institute of Technology)<\/p><\/td><\/tr>

Average-Distortion Sketching <\/em>
Yiqiao Bao, Anubhav Baweja, Nicolas Menand, Erik Waingarten, Nathan White, Tian Zhang (University of Pennsylvania)<\/p><\/td><\/tr>

Learning quantum Gibbs states locally and efficiently <\/em>
Chi-Fang Chen (UC Berkeley & MIT), Anurag Anshu, Quynh T. Nguyen (Harvard University)<\/p><\/td><\/tr>

Computational-Statistical Tradeoffs from NP-hardness <\/em>
Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan (Stanford University)<\/p><\/td><\/tr>

Overcomplete Tensor Decomposition via Koszul-Young Flattenings <\/em>
Pravesh K Kothari (Princeton University), Ankur Moitra (Massachusetts Institute of Technology), Alexander S Wein (UC Davis)<\/p><\/td><\/tr>

Faster Mixing of the Jerrum-Sinclair Chain <\/em>
Xiaoyu Chen (Nanjing University), Weiming Feng (The University of Hong Kong), Zhe Ju, Tianshun Miao, Yitong Yin, Xinyuan Zhang (Nanjing University)<\/p><\/td><\/tr>

The Proof Analysis Problem <\/em>
Noel Arteche (Lund University & University of Copenhagen), Albert Atserias (Universitat Polit\u00e8cnica de Catalunya), Susanna F. de Rezende (Lund University), Erfan Khaniki (University of Oxford)<\/p><\/td><\/tr>

Embeddings into Similarity Measures for Nearest Neighbor Search <\/em>
Alexandr Andoni (Columbia University, USA), Negev Shekel Nosatzki (Columbia University)<\/p><\/td><\/tr>

Quasipolynomial bounds for the corners theorem <\/em>
Michael Jaber (University of Texas, Austin), Yang P. Liu (Carnegie Mellon University), Shachar Lovett, Anthony Ostuni (University of California, San Diego), Mehtaab Sawhney (Columbia University)<\/p><\/td><\/tr>

Pattern Matching under Weighted Edit Distance <\/em>
Panagiotis Charalampopoulos (Birkbeck, University of London), Tomasz Kociumaka (Max Planck Institute for Informatics), Philip Wellnitz (National Institute of Informatics)<\/p><\/td><\/tr>

Faster logconcave sampling from a cold start in high dimension <\/em>
Yunbum Kook, Santosh S. Vempala (Georgia Institute of Technology)<\/p><\/td><\/tr>

Rapid Mixing on Random Regular Graphs beyond Uniqueness <\/em>
Xiaoyu Chen (Nanjing University), Zejia Chen (Shanghai Jiao Tong University), Zongchen Chen (Georgia Institute of Technology), Yitong Yin, Xinyuan Zhang (Nanjing University)<\/p><\/td><\/tr>

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs <\/em>
Shunhua Jiang (Columbia University), Michael Kapralov (EPFL, Switzerland), Lawrence Li Er Lu (University of Toronto), Aaron Sidford (Stanford University)<\/p><\/td><\/tr>

Proving Natural Distribution Properties is Harder than Testing Them <\/em>
Tal Herman (Weizmann Institute of Science), Guy Rothblum (Apple)<\/p><\/td><\/tr>

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa <\/em>
Benjamin Bedert, Tamio-Vesa Nakajima, Karolina Okrasa, Stanislav Zivny (University of Oxford)<\/p><\/td><\/tr>

On Inverse Theorems and Combinatorial Lines <\/em>
Amey Bhangale (UC Riverside), Subhash Khot (NYU), Yang Liu (Carnegie Mellon University), Dor Minzer (MIT)<\/p><\/td><\/tr>

Adaptivity Gaps for Stochastic Probing with Subadditive Functions <\/em>
Jian Li, Yinchen Liu, Yiran Zhang (Tsinghua University)<\/p><\/td><\/tr>

Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings) <\/em>
Lasse Wulf (Technical University of Denmark)<\/p><\/td><\/tr>

The Sponge is Quantum Indifferentiable <\/em>
Gorjan Alagic (University of Maryland and NIST), Joseph Carolan (University of Maryland, College Park), Christian Majenz, Saliha Tokat (Technical University of Denmark)<\/p><\/td><\/tr>

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams <\/em>
Sanjeev Khanna, Ashwin Padaki, Krish Singal, Erik Waingarten (University of Pennsylvania)<\/p><\/td><\/tr>

Adversarially robust quantum state learning and testing<\/em>
Maryam Aliakbarpour (Rice University), Vladimir Braverman (Johns Hopkins University, Google, Rice University), Nai-Hui Chia, Yuhan Liu (Rice University)<\/p><\/td><\/tr>

On Succinct Obfuscation via Propositional Logic (or: How to use pv-IO) <\/em>
Abhishek Jain (NTT Research and JHU), Zhengzhong Jin (Northeastern University), Surya Mathialagan (MIT), Omer Paneth (Tel Aviv University)<\/p><\/td><\/tr>

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration <\/em>
Shuichi Hirahara (National Institute for Informatics), Naoto Ohsaka (CyberAgent, Inc.)<\/p><\/td><\/tr>

Faster exact learning of k-term DNFs with membership and equivalence queries <\/em>
Josh Alman (Columbia University), Shivam Nadimpalli (MIT), Shyamal Patel, Rocco A. Servedio (Columbia University)<\/p><\/td><\/tr>

Tight Pair Query Lower Bounds for Matching and Earth Mover’s Distance <\/em>
Amir Azarmehr, Soheil Behnezhad (Northeastern University), Mohammad Roghani, Aviad Rubinstein (Stanford University)<\/p><\/td><\/tr>

RE-completeness of entangled constraint satisfaction problems <\/em>
Eric Culf, Kieran Mastel (University of Waterloo)<\/p><\/td><\/tr>

Succinct Homomorphic MACs from Groups and Applications <\/em>
Yuval Ishai (Technion), Hanjun Li, Huijia (Rachel) Lin (University of Washington)<\/p><\/td><\/tr>

Approximating High-Dimensional Earth Mover’s Distance as Fast as Closest Pair <\/em>
Lorenzo Beretta (University of California, Santa Cruz), Vincent Cohen-Addad, Rajesh Jayaram (Google Research), Erik Waingarten (University of Pennsylvania)<\/p><\/td><\/tr>

Undirected Multicast Network Coding Gaps via Locally Decodable Codes <\/em>
Zhongtian He, Mark Braverman (Princeton University)<\/p><\/td><\/tr>

Distance Approximating Minors for Planar and Minor-Free Graphs <\/em>
Hsien-Chih Chang, Jonathan Conroy (Department of Computer Science, Dartmouth College)<\/p><\/td><\/tr>

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance <\/em>
Debarati Das (Pennsylvania State University), Jacob Gilbert (University of Maryland), Tomasz Kociumaka (Max Planck Institute for Informatics), MohammadTaghi Hajiaghayi (University of Maryland), Barna Saha (University of California, San Diego)<\/p><\/td><\/tr>

Exponential improvements to the average-case hardness of BosonSampling <\/em>
Adam Bouland, Shaun Datta (Stanford University), Bill Fefferman (University of Chicago), Felipe Hernandez (Penn State)<\/p><\/td><\/tr>

Radial Isotropic Position via an Implicit Newton’s Method <\/em>
Arun Jambulapati (Independent), Jonathan Li, Kevin Tian (UT Austin)<\/p><\/td><\/tr>

Random-Shift Revisited: Tight Approximations for Tree Embeddings and \u21131-Oblivious Routings <\/em>
Maximilian Probst (ETH Z\u00fcrich), Rasmus Kyng, Tim Rieder (ETH Zurich)<\/p><\/td><\/tr>

High-to-Low Dimensional PPA-completeness: Borsuk-Ulam, Tucker, Consensus Halving, and Ham Sandwich <\/em>
Ruiquan Gao (Stanford University), Alexandros Hollender (University of Oxford), Aviad Rubinstein (Stanford)<\/p><\/td><\/tr>

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension <\/em>
Timothy M. Chan (University of Illinois at Urbana-Champaign), Hsien-Chih Chang (Department of Computer Science, Dartmouth College), Jie Gao (Rutgers University), S\u00e1ndor Kisfaludi-Bak (Aalto University), Hung Le (University of Massachusetts, Amherst, USA), Da Wei Zheng (University of Illinois at Urbana-Champaign)<\/p><\/td><\/tr>

Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics<\/em>
Hyung-Chan An (Yonsei University), Mong-Jen Kao (National Yang-Ming Chiao-Tung University), Changyeol Lee (Yonsei University), Mu-Ting Lee (National Yang-Ming Chiao-Tung University)<\/p><\/td><\/tr>

Rank Bounds and PIT for $\\Sigma^3 \\Pi \\Sigma \\Pi^d$ circuits via a non-linear Edelstein-Kelly theorem <\/em>
Abhibhav Garg, Rafael Oliveira, Akash Kumar Sengupta (University of Waterloo)<\/p><\/td><\/tr>

Dynamic Treewidth in Logarithmic Time <\/em>
Tuukka Korhonen (University of Copenhagen)<\/p><\/td><\/tr>

Polynomial-Time Approximation Schemes via Utility Alignment: Unit-Demand Pricing and More <\/em>
Robin Bowers (University of Colorado Boulder), Marius Garbea, Emmanouil Pountourakis (Drexel University), Samuel Taggart (Oberlin College)<\/p><\/td><\/tr>

Fast Algorithms for Graph Arboricity and Related Problems <\/em>
Ruoxu Cen (Duke University), Henry Fleischmann, George Z. Li, Jason Li (Carnegie Mellon University), Debmalya Panigrahi (Duke University)<\/p><\/td><\/tr>

Collapsing Catalytic Classes <\/em>
Michal Koucky (Computer Science Institute of Charles University, Prague), Ian Mertz (Charles University), Edward Pyne (MIT), Sasha Sami (Charles University)<\/p><\/td><\/tr>

Shortest Paths on Convex Polyhedral Surfaces <\/em>
Haitao Wang (University of Utah)<\/p><\/td><\/tr>

An Improved Bound for the Beck-Fiala Conjecture <\/em>
Nikhil Bansal (University of Michigan), Haotian Jiang (University of Chicago)<\/p><\/td><\/tr>

Deterministic Almost-Linear-Time Gomory-Hu Trees <\/em>
Amir Abboud (Weizmann Institute of Science), Rasmus Kyng (ETH Zurich), Jason Li (Carnegie Mellon University), Debmalya Panigrahi (Duke University), Maximilian Probst (ETH Zurich), Thatchaphol Saranurak (University of Michigan), Wuwei Yuan, Weixuan Yuan (ETH Zurich)<\/p><\/td><\/tr>

Near-Optimal Fault-Tolerant Strong Connectivity Preservers <\/em>
Gary Hoppenworth, Thatchaphol Saranurak, Benyu Wang (University of Michigan)<\/p><\/td><\/tr>

Improved 2-Approximate Shortest Paths for close vertex pairs <\/em>
Manoj Gupta (IIT Gandhinagar)<\/p><\/td><\/tr>

Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations <\/em>
Moni Naor (Weizmann Institue), Boaz Menuhin (Weizmann Instiute)<\/p><\/td><\/tr>

Improved Round-by-round Soundness IOPs via Reed-Muller Codes <\/em>
Dor Minzer, Kai Zhe Zheng (MIT)<\/p><\/td><\/tr>

Near-Optimal Algorithms for Omniprediction <\/em>
Princewill Okoroafor, Bobby Kleinberg, Michael Kim (Cornell University)<\/p><\/td><\/tr>

Almost Tight Additive Guarantees for $k$-Edge-Connectivity <\/em>
Nikhil Kumar, Chaitanya Swamy (University of Waterloo)<\/p><\/td><\/tr>

On optimal distinguishers for Planted Clique,<\/em>
Ansh Nagda (UC Berkeley), Prasad Raghavendra (U.C. Berkeley)<\/p><\/td><\/tr>

Constant Rate Codes for Adaptive Broadcasts Do Not Exist <\/em>
Klim Efremenko (Ben-Gurion University), Gillat Kol, Dmitry Paramonov (Princeton University), Raghuvansh Saxena (Tata Institute of Fundamental Research)<\/p><\/td><\/tr>

Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices <\/em>
Vijay Bhattiprolu (University of Waterloo), Venkatesan Guruswami (University of California, Berkeley), Euiwoong Lee (University of Michigan), Xuandi Ren (University of California, Berkeley)<\/p><\/td><\/tr>

Near-Optimal Property Testers for Pattern Matching <\/em>
Ce Jin (MIT), Tomasz Kociumaka (Max Planck Institute for Informatics)<\/p><\/td><\/tr>

Deterministic factorization of constant-depth algebraic circuits in subexponential time <\/em>
Somnath Bhattacharjee (University of Toronto), Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi (Tata Institute of Fundamental Research, Mumbai), Shubhangi Saraf (University of Toronto)<\/p><\/td><\/tr>

Integer multiplication is at least as hard as matrix transposition, <\/em>
David Harvey (UNSW Sydney), Joris van der Hoeven (Ecole Polytechnique)<\/p><\/td><\/tr>

A k^{q\/q-2} Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs <\/em>
Oliver Janzer (EPFL), Peter Manohar (The Institute for Advanced Study)<\/p><\/td><\/tr>

Online Edge Coloring: Sharp Thresholds <\/em>
Joakim Blikstad (CWI), Ola Svensson, Radu Vintan (EPFL), David Wajc (Technion)<\/p><\/td><\/tr>

Gap-preserving reductions and RE-completeness of Independent Set Games <\/em>
Laura Man\u010dinska, Pieter Spaas, Taro Spirig (University of Copenhagen), Matthijs Vernooij (TU Delft)<\/p><\/td><\/tr>

On the Parallel Complexity of Finding a Matroid Basis <\/em>
Sanjeev Khanna (University of Pennsylvania), Aaron Putterman (Harvard University), Junkai Song (University of Pennsylvania)<\/p><\/td><\/tr>

Bipartite Matching is in Catalytic Logspace <\/em>
Aryan Agarwala (Max Planck Institute for Informatics), Ian Mertz (Charles University)<\/p><\/td><\/tr>

Distributed Triangle Detection is Hard in Few Rounds <\/em>
Sepehr Assadi, Janani Sundaresan (University of Waterloo)<\/p><\/td><\/tr>

Weighted k-Path and Other Problems in Almost O*(2^k) Deterministic Time via Dynamic Representative Sets<\/em>
Jesper Nederlof (Utrecht University)<\/p><\/td><\/tr>

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs <\/em>
Aaron Bernstein (New York University), Joakim Blikstad (CWI), Jason Li (Carnegie Mellon University), Thatchaphol Saranurak (University of Michigan), Ta-Wei Tu (Stanford University)<\/p><\/td><\/tr>

Random Reed-Solomon Codes and Random Linear Codes are Locally Equivalent <\/em>
Matan Levi, Jonathan Mosheiff (Ben-Gurion University), Nikhil Shagrithaya (University of Michigan, Ann Arbor)<\/p><\/td><\/tr>

Kronecker Powers, Orthogonal Vectors, and the\u00a0Asymptotic Spectrum<\/em>
Josh Alman (Columbia University), Baitian Li (Tsinghua University)<\/p><\/td><\/tr>

Robust Learning of Multi-index Models via Iterative Subspace Approximation <\/em>
Ilias Diakonikolas, Giannis Iakovidis (University of Wisconsin-Madison), Daniel M. Kane (University of California, San Diego), Nikos Zarifis (University of Wisconsin-Madison)<\/p><\/td><\/tr>

Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions <\/em>
Rahul Ilango (MIT), Alex Lombardi (Princeton)<\/p><\/td><\/tr>

Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models <\/em>
Ilias Diakonikolas (UW Madison), Daniel Kane (University of California, San Diego)<\/p><\/td><\/tr>

Sign-Rank of k-Hamming Distance is Constant <\/em>
Mika G\u00f6\u00f6s, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov (EPFL)<\/p><\/td><\/tr>

Incompressibility and spectral gaps of random circuits <\/em>
Chi-Fang Chen (MIT), Jeongwan Haah (Stanford), Jonas Haferkamp, Yunchao Liu (Harvard University), Tony Metger (ETH Zurich), Xinyu Tan (MIT)<\/p><\/td><\/tr>

Robust Local Testability of Tensor Products of Constant-Rate Algebraic Geometry Codes,<\/em>
Sumegha Garg (Rutgers University), Akash Kumar Sengupta (University of Waterloo)<\/p><\/td><\/tr>

Truthful and Almost Envy-Free Mechanism of Allocating Indivisible Goods: the Power of Randomness <\/em>
Xiaolin Bu, Biaoshuai Tao (Shanghai Jiao Tong University)<\/p><\/td><\/tr>

How Global Calibration Strengthens Multiaccuracy <\/em>
S\u00edlvia Casacuberta (University of Oxford), Parikshit Gopalan (Apple), Varun Kanade (University of Oxford), Omer Reingold (Stanford University)<\/p><\/td><\/tr>

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences <\/em>
Jonathan Leake (University of Waterloo), Kasper Lindberg (ETH Zurich), Shayan Oveis Gharan (University of Washington)<\/p><\/td><\/tr>

More efficient sifting for grid norms, and applications to multiparty communication complexity <\/em>
Zander Kelley (IAS), Xin Lyu (UC berkeley)<\/p><\/td><\/tr>

Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set <\/em>
Mohsen Ghaffari (MIT), Christoph Grunau (ETH Zurich)<\/p><\/td><\/tr>

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems <\/em>
Alberto Larrauri (Durham University)<\/p><\/td><\/tr>

Instance-Optimal Uniformity Testing and Tracking <\/em>
Guy Blanc (Stanford University), Cl\u00e9ment Canonne (University of Sydney), Erik Waingarten (University of Pennsylvania)<\/p><\/td><\/tr>

Binary Codes for Computationally Bounded Errors Under Standard Crypto Assumptions <\/em>
George Lu (UT Austin), Jad Silbak (Northeastern University), Daniel Wichs (Northeastern University and NTT Research)<\/p><\/td><\/tr>

Optimal Smoothed Analysis of the Simplex Method <\/em>
Eleon Bach (EPFL), Sophie Huiberts (CNRS)<\/p><\/td><\/tr>

Improved Lower Bounds for all Odd-Query Locally Decodable Codes <\/em>
Arpon Basu (Princeton University), Jun-Ting Hsieh (Carnegie Mellon University), Pravesh K. Kothari (Princeton University and IAS), Andrew D. Lin (Princeton University)<\/p><\/td><\/tr>

Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness <\/em>
Vladimir Lysikov, Michael Walter (Ruhr University Bochum)<\/p><\/td><\/tr>

Lower Bounds for Non-adaptive Local Computation Algorithms <\/em>
Amir Azarmehr, Soheil Behnezhad, Alma Ghafari (Northeastern University), Madhu Sudan (Harvard)<\/p><\/td><\/tr>

Polynomial Bounds for the Graph Minor Structure Theorem <\/em>
Maximilian Gorsky (Institute for Basic Science (IBS), Daejeon, South Korea), Micha\u0142 Seweryn (Charles University, Prague, Czech Republic), Sebastian Wiederrecht (KAIST, Daejeon, South Korea)<\/p><\/td><\/tr>

Finding Colorings in One-Sided Expanders <\/em>
Rares-Darius Buhai (ETH Zurich), Yiding Hua (ETH Z\u00fcrich), David Steurer, Andor V\u00e1ri-Kakas (ETH Zurich)<\/p><\/td><\/tr>

Explicit Lossless Vertex Expanders <\/em>
Jun-Ting Hsieh (Carnegie Mellon University), Alexander Lubotzky (Weizmann), Sidhanth Mohanty (MIT), Assaf Reiner (HUJI), Rachel Yun Zhang (MIT)<\/p><\/td><\/tr>

Extractors for Samplable Distributions with Polynomially Small Min-Entropy <\/em>
Ronen Shaltiel (University of Haifa)<\/p><\/td><\/tr>

Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching <\/em>
Seri Khoury (INSAIT), Aaron Schild (Google Research)<\/p><\/td><\/tr>

Constant Approximation of Arboricity in Near-Optimal Sublinear Time <\/em>
Jiangqi Dai, Mohsen Ghaffari (MIT), Julian Portmann (ETH Zurich)<\/p><\/td><\/tr>

Solving Zero-Sum Games with Fewer Matrix-Vector Products <\/em>
Ishani Karmarkar, Liam O’Carroll, Aaron Sidford (Stanford University)<\/p><\/td><\/tr>

Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade <\/em>
Simone Di Gregorio (Sapienza), Paul Duetting (Google), Federico Fusco (Sapienza University of Rome), Chris Schwiegelshohn (Aarhus University)<\/p><\/td><\/tr>

Characterization of Priority-Neutral Matching Lattices <\/em>
Clayton Thomas (Microsoft Research)<\/p><\/td><\/tr>

\u21132\/\u21132 Sparse Recovery via Weighted Hypergraph Peeling <\/em>
Nick Fischer (INSAIT), Vasileios Nakos (National and Kapodistrian University of Athens and Archimedes, Athena Research Center, Greece)<\/p><\/td><\/tr>

Stochastic scheduling with Bernoulli-type jobs through policy stratification <\/em>
Antonios Antoniadis, Ruben Hoeksma (University of Twente), Kevin Schewior (University of Cologne), Marc Uetz (University of Twente)<\/p><\/td><\/tr>

Query-Efficient Fixpoints of $\\ell_p$-Contractions <\/em>
Sebastian Haslebacher, Jonas Lill (ETH Z\u00fcrich), Patrick Schnider (University of Basel and ETH Z\u00fcrich), Simon Weber (ETH Z\u00fcrich)<\/p><\/td><\/tr>

Breaking a Long-Standing Barrier: 2-$\\varepsilon$ Approximation for Steiner Forest <\/em>
Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Mohammad Mahdavi (University of Maryland)<\/p><\/td><\/tr>

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut <\/em>
Yumou Fei, Dor Minzer, Shuo Wang (MIT)<\/p><\/td><\/tr>

A Little Clairvoyance Is All You Need <\/em>
Anupam Gupta (New York University, USA), Haim Kaplan (Tel Aviv University), Alexander Lindermayr (University of Bremen), Jens Schl\u00f6ter (CWI), Sorrachai Yingchareonthawornchai (ETH Zurich)<\/p><\/td><\/tr>

Cycle-factors of regular graphs via entropy <\/em>
Eoin Hurley, Antonio Girao, Lukas Michel, Nemanja Draganic, Alp M\u00fcyesser (University of Oxford), Micha Christoph (ETH Zurich)<\/p><\/td><\/tr>

Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives <\/em>
Thomas Kesselheim (University of Bonn), Marco Molinaro (Microsoft Research Redmond), Kalen Patton, Sahil Singla (Georgia Institute of Technology)<\/p><\/td><\/tr>

Stochastic Knapsack without Relaxing the Capacity <\/em>
Anindya De, Sanjeev Khanna, Nathan White (University of Pennsylvania)<\/p><\/td><\/tr>

Root Ridge Leverage Score Sampling for $\\ell_p$ Subspace Approximation <\/em>
David P. Woodruff (Carnegie Mellon University), Taisuke Yasuda (The Voleon Group)<\/p><\/td><\/tr>

Parallel Repetition for Post-Quantum Arguments <\/em>
Andrew Huang, Yael Tauman Kalai (MIT)<\/p><\/td><\/tr>

Perfect L_p Sampling with Polylogarithmic Update Time <\/em>
William Swartworth, David P. Woodruff (Carnegie Mellon University), Samson Zhou (Texas A&M University)<\/p><\/td><\/tr>

The Quasi-Polynomial Low-Degree Conjecture is False <\/em>
Rares-Darius Buhai (ETH Zurich), Jun-Ting Hsieh, Aayush Jain (Carnegie Mellon University), Pravesh Kothari (Princeton University)<\/p><\/td><\/tr>

Optimal 4-Approximation for the Correlated Pandora\u2019s Problem <\/em>
Nikhil Bansal (University of Michigan), Zhiyi Huang, Zixuan Zhu (The University of Hong Kong)<\/p><\/td><\/tr>

PTF Testing Lower Bounds for Non-Gaussian Component Analysis <\/em>
Ilias Diakonikolas (UW Madison), Daniel M. Kane (University of California, San Diego), Sihan Liu (UCSD), Thanasis Pittas (UW Madison)<\/p><\/td><\/tr>

Parallel $(1+\\epsilon)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work <\/em>
Bernhard Haeupler (INSAIT, Sofia University “”St. Kliment Ohridski”” & ETH Zurich), Yonggang Jiang (Max Planck Institute for Informatics and Saarland University), Yaowei Long, Thatchaphol Saranurak (University of Michigan), Shengzhe Wang (ETH Z\u00fcrich)<\/p><\/td><\/tr>

Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses,<\/em>
Mark Sellke (Harvard)<\/p><\/td><\/tr>

An Improved Greedy Approximation for (Metric) $k$-Means <\/em>
Moses Charikar (Stanford University), Vincent Cohen-Addad (Google Research), Ruiquan Gao (Stanford University), Fabrizio Grandoni (IDSIA, USI-SUPSI), Euiwoong Lee (University of Michigan), Ernest van Wijland (Universit\u00e9 Paris-Cit\u00e9)<\/p><\/td><\/tr>

A distillation\u2013teleportation protocol for fault-tolerant QRAM <\/em>
Alexander Dalzell, Connor T. Hann (AWS Center for Quantum Computing), Andr\u00e1s Gily\u00e9n (HUN-REN Alfr\u00e9d R\u00e9nyi Institute of Mathematics, Budapest), Sam McArdle (AWS Center for Quantum Computing), Grant Salton (Amazon Quantum Solutions Lab), Quynh Nguyen (Harvard University), Aleksander Kubica (Yale), Fernando Brandao (Amazon\/Caltech)<\/p><\/td><\/tr>

Static Retrieval Revisited: To Optimality and Beyond <\/em>
Yang Hu (Tsinghua University), William Kuszmaul, Jingxun Liang (CMU), Huacheng Yu (Princeton University), Junkai Zhang (Tsinghua University), Renfei Zhou (CMU)<\/p><\/td><\/tr>

Beyond Regularity: Simple versus Optimal Mechanisms, Revisited <\/em>
Yiding Feng (Hong Kong University of Science and Technology), Yaonan Jin (Huawei TCS Lab)<\/p><\/td><\/tr>

Factorization Norms and an Inverse Theorem for MaxCut<\/em>
Igor Balla (Simons Laufer Mathematical Sciences Institute), Lianna Hambardzumyan (University of Victoria), Istvan Tomon (Umea University)<\/p><\/td><\/tr>

On the Impossibility of SNARGs with Short CRS (or: Revisiting Gentry-Wichs Barrier in the Non-adaptive Setting) <\/em>
Liyan Chen (Tsinghua University), Zhengzhong Jin (Northeastern)<\/p><\/td><\/tr>

Paths and Intersections: Exact Emulators for Planar Graphs <\/em>
George Z. Li (Carnegie Mellon University), Zihan Tan (Rutgers University), Tianyi Zhang (ETH Zurich)<\/p><\/td><\/tr>

Ramanujan bigraphs and applications <\/em>
Shai Evra (Hebrew University of Jerusalem), Brooke Feigon (CUNY), Ori Parzanchevski (Hebrew University of Jerusalem), Kathrin Maurischat (RWTH Aachen University)<\/p><\/td><\/tr>

Stronger Cell Probe Lower Bounds via Local PRGs <\/em>
Oliver Korten, Toniann Pitassi (Columbia University), Russell Impagliazzo (University of California, San Diego)<\/p><\/td><\/tr>

A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number <\/em>
Romain Bourneuf (LaBRI), Pierre Charbit (IRIF, Universit\u00e9 Paris Cit\u00e9), Stephan Thomasse (ENS Lyon)<\/p><\/td><\/tr>

Edge-weighted Matching in the Dark <\/em>
Zhiyi Huang, Enze Sun (The University of Hong Kong), Xiaowei Wu (University of Macau), Jiahao Zhao (The University of Hong Kong)<\/p><\/td><\/tr>

Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks <\/em>
Louis Golowich, Venkatesan Guruswami (UC Berkeley)<\/p><\/td><\/tr>

NP-hardness of the Minimum Circuit Size Problem from Well-Studied Assumptions <\/em>
Shuichi Hirahara (National Institute for Informatics), Rahul Ilango (Massachusetts Institute of Technology)<\/p><\/td><\/tr>

Density Measures for Language Generation <\/em>
Jon Kleinberg (Cornell), Fan Wei (Duke University, USA)<\/p><\/td><\/tr>

Fingerprint Filters are Optimal <\/em>
William Kuszmaul, Jingxun Liang, Renfei Zhou (Carnegie Mellon University)<\/p><\/td><\/tr>

Efficiently Batching Unambiguous Interactive Proofs <\/em>
Bonnie Berger, Rohan Goyal, Matthew M. Hong, Yael Tauman Kalai (MIT)<\/p><\/td><\/tr>

Direct Product Theorems for Randomized Query Complexity <\/em>
Shalev Ben-David, Eric Blais (University of Waterloo)<\/p><\/td><\/tr>

Deterministic counting from coupling independence <\/em>
Xiaoyu Chen (Nanjing University), Weiming Feng (The University of Hong Kong), Heng Guo (University of Edinburgh), Xinyuan Zhang, Zongrui Zou (Nanjing University)<\/p><\/td><\/tr>

Theoretical limitations of multi-layer Transformer <\/em>
Lijie Chen (University of California at Berkeley), Binghui Peng (Stanford University), Hongxun Wu (University of California at Berkeley)<\/p><\/td><\/tr>

High dimensional online calibration in polynomial time <\/em>
Binghui Peng (Stanford)<\/p><\/td><\/tr>

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time <\/em>
Shashank Srivastava (DIMACS (Rutgers) & IAS), Madhur Tulsiani (Toyota Technological Institute at Chicago, USA)<\/p><\/td><\/tr><\/tbody><\/table>\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 2025 Accepted Papers (The paper order has been randomized.) The Power of Recursive Embeddings for $ell_p$ Metrics Robert Krauthgamer, Nir Petruschka, Shay Sapir (Weizmann Institute) Group Order is in QCMA Fran\u00e7ois Le Gall, Harumichi Nishimura, Dhara Thakkar (Nagoya University) Maximally Extendable Product Codes are Good Coboundary Expanders Gleb Kalachev, Pavel Panteleev (Moscow State University) […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-82","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/pages\/82","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/comments?post=82"}],"version-history":[{"count":0,"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/pages\/82\/revisions"}],"wp:attachment":[{"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/media?parent=82"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}