| 2025 | 66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, Sydney, Australia, December 14-17, 2025 |
| 2025 | A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number. Romain Bourneuf, Pierre Charbit, Stéphan Thomassé |
| 2025 | A Distillation-Teleportation Protocol for Fault-Tolerant QRAM. Alexander M. Dalzell, András Gilyén, Connor T. Hann, Sam McArdle, Grant Salton, Quynh T. Nguyen, Aleksander Kubica, Fernando G. S. L. Brandão |
| 2025 | A Little Clairvoyance Is All You Need. Anupam Gupta, Haim Kaplan, Alexander Lindermayr, Jens Schlöter, Sorrachai Yingchareonthawornchai |
| 2025 | A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams. Sanjeev Khanna, Ashwin Padaki, Krish Singal, Erik Waingarten |
| 2025 | A k Oliver Janzer, Peter Manohar |
| 2025 | Adaptivity Gaps for Stochastic Probing with Subadditive Functions. Jian Li, Yinchen Liu, Yiran Zhang |
| 2025 | Adversarially Robust Quantum State Learning and Testing. Maryam Aliakbarpour, Vladimir Braverman, Nai-Hui Chia, Yuhan Liu |
| 2025 | Almost Tight Additive Guarantees for k-Edge-Connectivity. Nikhil Kumar, Chaitanya Swamy |
| 2025 | An Improved Bound for the Beck-Fiala Conjecture. Nikhil Bansal, Haotian Jiang |
| 2025 | An Improved Greedy Approximation for (Metric) k-Means. Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, Ernest van Wijland |
| 2025 | Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair. Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram, Erik Waingarten |
| 2025 | Asymptotically Optimal Inapproximability of Ek-SAT Reconfiguration. Shuichi Hirahara, Naoto Ohsaka |
| 2025 | Average Distortion Sketching. Yiqiao Bao, Anubhav Baweja, Nicolas Menand, Erik Waingarten, Nathan White, Tian Zhang |
| 2025 | Beyond Regularity: Simple versus Optimal Mechanisms, Revisited. Yiding Feng, Yaonan Jin |
| 2025 | Binary Codes for Computationally Bounded Errors Under Standard Crypto Assumptions. George Lu, Jad Silbak, Daniel Wichs |
| 2025 | Bipartite Matching is in Catalytic Logspace. Aryan Agarwala, Ian Mertz |
| 2025 | Breaking a Long-Standing Barrier: 2-ε Approximation for Steiner Forest. Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Mohammad Mahdavi |
| 2025 | Characterization of Priority-Neutral Matching Lattices. Clayton Thomas |
| 2025 | Collapsing Catalytic Classes. Michal Koucký, Ian Mertz, Edward Pyne, Sasha Sami |
| 2025 | Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs. Aaron Bernstein, Joakim Blikstad, Jason Li, Thatchaphol Saranurak, Ta-Wei Tu |
| 2025 | Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness. Vladimir Lysikov, Michael Walter |
| 2025 | Computational-Statistical Tradeoffs from NP-hardness. Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan |
| 2025 | Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings). Lasse Wulf |
| 2025 | Constant Approximation of Arboricity in Near-Optimal Sublinear Time. Jiangqi Dai, Mohsen Ghaffari, Julian Portmann |
| 2025 | Constant Rate Codes for Adaptive Broadcasts Do Not Exist. Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena |
| 2025 | Cryptography Meets Worst-case Complexity: Optimal Security and More From iO and Worst-case Assumptions. Rahul Ilango, Alex Lombardi |
| 2025 | Cycle-factors of regular graphs via entropy. Micha Christoph, Nemanja Draganic, António Girão, Eoin Hurley, Lukas Michel, Alp Müyesser |
| 2025 | Density Measures for Language Generation. Jon M. Kleinberg, Fan Wei |
| 2025 | Deterministic Almost-Linear-Time Gomory-Hu Trees. Amir Abboud, Rasmus Kyng, Jason Li, Debmalya Panigrahi, Maximilian Probst Gutenberg, Thatchaphol Saranurak, Weixuan Yuan, Wuwei Yuan |
| 2025 | Deterministic Counting from Coupling Independence. Xiaoyu Chen, Weiming Feng, Heng Guo, Xinyuan Zhang, Zongrui Zou |
| 2025 | Deterministic factorization of constant-depth algebraic circuits in subexponential time. Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf |
| 2025 | Direct Product Theorems for Randomized Query Complexity. Shalev Ben-David, Eric Blais |
| 2025 | Distance Approximating Minors for Planar and Minor-Free Graphs. Hsien-Chih Chang, Jonathan Conroy |
| 2025 | Distributed Triangle Detection is Hard in Few Rounds. Sepehr Assadi, Janani Sundaresan |
| 2025 | Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance. Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha |
| 2025 | Dynamic Treewidth in Logarithmic Time. Tuukka Korhonen |
| 2025 | Edge-weighted Matching in the Dark. Zhiyi Huang, Enze Sun, Xiaowei Wu, Jiahao Zhao |
| 2025 | Efficiently Batching Unambiguous Interactive Proofs. Bonnie Berger, Rohan Goyal, Matthew M. Hong, Yael Tauman Kalai |
| 2025 | Embeddings into Similarity Measures for Nearest Neighbor Search. Alexandr Andoni, Negev Shekel Nosatzki |
| 2025 | Explicit Lossless Vertex Expanders. Jun-Ting Hsieh, Alexander Lubotzky, Sidhanth Mohanty, Assaf Reiner, Rachel Yun Zhang |
| 2025 | Exponential improvements to the average-case hardness of BosonSampling. Adam Bouland, Ishaun Datta, Bill Fefferman, Felipe Hernandez |
| 2025 | Extractors for Samplable Distributions with Polynomially Small Min-Entropy. Ronen Shaltiel |
| 2025 | Factorization norms and an inverse theorem for MaxCut. Igor Balla, Lianna Hambardzumyan, István Tomon |
| 2025 | Fast Algorithms for Graph Arboricity and Related Problems. Ruoxu Cen, Henry L. Fleischmann, George Z. Li, Jason Li, Debmalya Panigrahi |
| 2025 | Faster Exact Learning of k-Term DNFs with Membership and Equivalence Queries. Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio |
| 2025 | Faster Logconcave Sampling from a Cold Start in High Dimension. Yunbum Kook, Santosh S. Vempala |
| 2025 | Faster Mixing of the Jerrum-Sinclair Chain. Xiaoyu Chen, Weiming Feng, Zhe Ju, Tianshun Miao, Yitong Yin, Xinyuan Zhang |
| 2025 | Finding Colorings in One-Sided Expanders. Rares-Darius Buhai, Yiding Hua, David Steurer, Andor Vári-Kakas |
| 2025 | Fingerprint Filters Are Optimal. William Kuszmaul, Jingxun Liang, Renfei Zhou |
| 2025 | Gap-preserving reductions and RE-completeness of independent set games. Laura Mancinska, Pieter Spaas, Taro Spirig, Matthijs Vernooij |
| 2025 | Generalized Flow in Nearly-linear Time on Moderately Dense Graphs. Shunhua Jiang, Michael Kapralov, Lawrence Li, Aaron Sidford |
| 2025 | Group Order is in QCMA. François Le Gall, Harumichi Nishimura, Dhara Thakkar |
| 2025 | Gödel in Cryptography: Effectively Zero-Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness. Rahul Ilango |
| 2025 | Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics. Hyung-Chan An, Mong-Jen Kao, Changyeol Lee, Mu-Ting Lee |
| 2025 | High-to-Low Dimensional PPA-completeness: Borsuk-Ulam, Tucker, Consensus Halving, and Ham Sandwich. Ruiquan Gao, Alexandros Hollender, Aviad Rubinstein |
| 2025 | How Global Calibration Strengthens Multiaccuracy. Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade, Omer Reingold |
| 2025 | Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models. Ilias Diakonikolas, Daniel M. Kane |
| 2025 | Improved 2-Approximate Shortest Paths for close vertex pairs. Manoj Gupta |
| 2025 | Improved Lower Bounds for all Odd-Query Locally Decodable Codes. Arpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari, Andrew D. Lin |
| 2025 | Improved Round-by-round Soundness IOPs via Reed-Muller Codes. Dor Minzer, Kai Zhe Zheng |
| 2025 | Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices. Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee, Xuandi Ren |
| 2025 | Incompressibility and Spectral Gaps of Random Circuits. Chi-Fang Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu, Tony Metger, Xinyu Tan |
| 2025 | Ineffectiveness for Search and Undecidability of PCSP Meta-Problems. Alberto Larrauri |
| 2025 | Instance-Optimal Uniformity Testing and Tracking. Guy Blanc, Clément L. Canonne, Erik Waingarten |
| 2025 | Integer multiplication is at least as hard as matrix transposition. David Harvey, Joris van der Hoeven |
| 2025 | Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives. Thomas Kesselheim, Marco Molinaro, Kalen Patton, Sahil Singla |
| 2025 | Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum. Josh Alman, Baitian Li |
| 2025 | Learning quantum Gibbs states locally and efficiently. Chi-Fang Chen, Anurag Anshu, Quynh T. Nguyen |
| 2025 | List Decoding Expander-Based Codes up to Capacity in Near-Linear Time. Shashank Srivastava, Madhur Tulsiani |
| 2025 | Lower Bounds for Non-adaptive Local Computation Algorithms. Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Madhu Sudan |
| 2025 | Maximally Extendable Product Codes are Good Coboundary Expanders. Gleb Kalachev, Pavel Panteleev |
| 2025 | More efficient sifting for grid norms, and applications to multiparty communication complexity. Zander Kelley, Xin Lyu |
| 2025 | Multi-Pass Streaming Lower Bounds for Approximating Max-Cut. Yumou Fei, Dor Minzer, Shuo Wang |
| 2025 | NP-hardness of the Minimum Circuit Size Problem from Well-Studied Assumptions. Shuichi Hirahara, Rahul Ilango |
| 2025 | Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks. Louis Golowich, Venkatesan Guruswami |
| 2025 | Near-Optimal Algorithms for Omniprediction. Princewill Okoroafor, Robert Kleinberg, Michael P. Kim |
| 2025 | Near-Optimal Fault-Tolerant Strong Connectivity Preservers. Gary Hoppenworth, Thatchaphol Saranurak, Benyu Wang |
| 2025 | Near-Optimal Property Testers for Pattern Matching. Ce Jin, Tomasz Kociumaka |
| 2025 | Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade. Simone Di Gregorio, Paul Dütting, Federico Fusco, Chris Schwiegelshohn |
| 2025 | Obfuscation of Unitary Quantum Programs. Mi-Ying Miryam Huang, Er-Cheng Tang |
| 2025 | On Inverse Theorems and Combinatorial Lines. Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer |
| 2025 | On Succinct Obfuscation via Propositional Proofs. Abhishek Jain, Zhengzhong Jin, Surya Mathialagan, Omer Paneth |
| 2025 | On optimal distinguishers for Planted Clique. Ansh Nagda, Prasad Raghavendra |
| 2025 | On the Impossibility of SNARGs with Short CRS : (or: Revisiting Gentry-Wichs Barrier in the Non-adaptive Setting). Liyan Chen, Zhengzhong Jin |
| 2025 | On the Parallel Complexity of Finding a Matroid Basis. Sanjeev Khanna, Aaron Putterman, Junkai Song |
| 2025 | Online Edge Coloring: Sharp Thresholds. Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc |
| 2025 | Optimal 4-Approximation for the Correlated Pandora's Problem. Nikhil Bansal, Zhiyi Huang, Zixuan Zhu |
| 2025 | Optimal Smoothed Analysis of the Simplex Method. Eleon Bach, Sophie Huiberts |
| 2025 | Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences. Jonathan Leake, Kasper Lindberg, Shayan Oveis Gharan |
| 2025 | Overcomplete Tensor Decomposition via Koszul-Young Flattenings. Pravesh K. Kothari, Ankur Moitra, Alexander S. Wein |
| 2025 | PTF Testing Lower Bounds for Non-Gaussian Component Analysis. Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, Thanasis Pittas |
| 2025 | Parallel (1+ε)-Approximate Multi-Commodity Min-Cost Flow in Almost Optimal Depth and Work. Bernhard Haeupler, Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak, Shengzhe Wang |
| 2025 | Parallel Repetition for Post-Quantum Arguments. Andrew Huang, Yael Tauman Kalai |
| 2025 | Paths and Intersections: Exact Emulators for Planar Graphs. George Z. Li, Zihan Tan, Tianyi Zhang |
| 2025 | Pattern Matching under Weighted Edit Distance. Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz |
| 2025 | Perfect Lp Sampling with Polylogarithmic Update Time. William Swartworth, David P. Woodruff, Samson Zhou |
| 2025 | Polynomial bounds for the Graph Minor Structure Theorem. Maximilian Gorsky, Michal T. Seweryn, Sebastian Wiederrecht |
| 2025 | Polynomial-Time Approximation Schemes via Utility Alignment: Unit-Demand Pricing and More. Robin Bowers, Marius Garbea, Emmanouil Pountourakis, Samuel Taggart |
| 2025 | Proving Natural Distribution Properties is Harder than Testing Them. Tal Herman, Guy N. Rothblum |
| 2025 | Quasipolynomial Bounds for the Corners Theorem. Michael Jaber, Yang P. Liu, Shachar Lovett, Anthony Ostuni, Mehtaab Sawhney |
| 2025 | Query-Efficient Fixpoints of ℓp-Contractions. Sebastian Haslebacher, Jonas Lill, Patrick Schnider, Simon Weber |
| 2025 | RE-completeness of entangled constraint satisfaction problems. Eric Culf, Kieran Mastel |
| 2025 | Radial Isotropic Position via an Implicit Newton's Method. Arun Jambulapati, Jonathan Li, Kevin Tian |
| 2025 | Ramanujan bigraphs and applications. Shai Evra, Brooke Feigon, Kathrin Maurischat, Ori Parzanchevski |
| 2025 | Random Reed-Solomon Codes and Random Linear Codes are Locally Equivalent. Matan Levi, Jonathan Mosheiff, Nikhil Shagrithaya |
| 2025 | Random-Shift Revisited: Tight Approximations for Tree Embeddings and ℓ₁-Oblivious Routings. Rasmus Kyng, Maximilian Probst Gutenberg, Tim Rieder |
| 2025 | Rank Bounds and PIT for depth-4 circuits with top fan-in 3 and constant bottom fan-in via a non-linear Edelstein-Kelly theorem. Abhibhav Garg, Rafael Oliveira, Akash Kumar Sengupta |
| 2025 | Rapid Mixing on Random Regular Graphs beyond Uniqueness. Xiaoyu Chen, Zejia Chen, Zongchen Chen, Yitong Yin, Xinyuan Zhang |
| 2025 | Robust Learning of Multi-index Models via Iterative Subspace Approximation. Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Nikos Zarifis |
| 2025 | Robust Local Testability of Tensor Products of Constant-Rate Algebraic Geometry Codes. Sumegha Garg, Akash Kumar Sengupta |
| 2025 | Root Ridge Leverage Score Sampling for ℓp Subspace Approximation. David P. Woodruff, Taisuke Yasuda |
| 2025 | Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching. Seri Khoury, Aaron Schild |
| 2025 | Shortest Paths on Convex Polyhedral Surfaces. Haitao Wang |
| 2025 | Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations. Boaz Menuhin, Moni Naor |
| 2025 | Sign-Rank of k-Hamming Distance is Constant. Mika Göös, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov |
| 2025 | Solving Linear Inequalities over the Space of Convex Sets & its Applications to Cryptography and Hydrodynamics. Saugata Basu, Hamidreza Amini Khorasgani, Hemanta K. Maji, Hai H. Nguyen |
| 2025 | Solving Zero-Sum Games with Fewer Matrix-Vector Products. Ishani Karmarkar, Liam O'Carroll, Aaron Sidford |
| 2025 | Static Retrieval Revisited: To Optimality and Beyond. Yang Hu, William Kuszmaul, Jingxun Liang, Huacheng Yu, Junkai Zhang, Renfei Zhou |
| 2025 | Stochastic Knapsack without Relaxing the Capacity. Anindya De, Sanjeev Khanna, Nathan White |
| 2025 | Stochastic scheduling with Bernoulli-type jobs through policy stratification. Antonios Antoniadis, Ruben Hoeksma, Kevin Schewior, Marc Uetz |
| 2025 | Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa. Benjamin Bedert, Tamio-Vesa Nakajima, Karolina Okrasa, Stanislav Zivný |
| 2025 | Stronger Cell Probe Lower Bounds via Local PRGs. Oliver Korten, Toniann Pitassi, Russell Impagliazzo |
| 2025 | Succinct Homomorphic MACs from Groups and Applications. Yuval Ishai, Hanjun Li, Huijia Lin |
| 2025 | The Power of Recursive Embeddings for ℓp Metrics. Robert Krauthgamer, Nir Petruschka, Shay Sapir |
| 2025 | The Proof Analysis Problem. Noel Arteche, Albert Atserias, Susanna F. de Rezende, Erfan Khaniki |
| 2025 | The Quasi-Polynomial Low-Degree Conjecture is False. Rares-Darius Buhai, Jun-Ting Hsieh, Aayush Jain, Pravesh K. Kothari |
| 2025 | The Sponge Is Quantum Indifferentiable. Gorjan Alagic, Joseph Carolan, Christian Majenz, Saliha Tokat |
| 2025 | Theoretical limitations of multi-layer Transformer. Lijie Chen, Binghui Peng, Hongxun Wu |
| 2025 | Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses. Mark Sellke |
| 2025 | Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance. Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein |
| 2025 | Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set. Mohsen Ghaffari, Christoph Grunau |
| 2025 | Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension. Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, Da Wei Zheng |
| 2025 | Truthful and Almost Envy-Free Mechanism of Allocating Indivisible Goods: the Power of Randomness. Xiaolin Bu, Biaoshuai Tao |
| 2025 | Undirected Multicast Network Coding Gaps via Locally Decodable Codes. Mark Braverman, Zhongtian He |
| 2025 | Weighted k-Path and Other Problems in Almost O Jesper Nederlof |
| 2025 | ℓ2/ℓ2 Sparse Recovery via Weighted Hypergraph Peeling. Nick Fischer, Vasileios Nakos |