| 2025 | A (2+ε)-Approximation Algorithm for Metric k-Median. Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn, Ola Svensson |
| 2025 | A 5/4-Approximation for Two-Edge Connectivity. Miguel Bosch-Calvo, Mohit Garg, Fabrizio Grandoni, Felix Hommelsheim, Afrouz Jabal Ameli, Alexander Lindermayr |
| 2025 | A Bound on the Quantum Value of All Compiled Nonlocal Games. Alexander Kulpe, Giulio Malavolta, Connor Paddock, Simon Schmidt, Michael Walter |
| 2025 | A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends. Karl Bringmann, Egor Gorbachev |
| 2025 | A Framework for Building Data Structures from Communication Protocols. Alexandr Andoni, Shunhua Jiang, Omri Weinstein |
| 2025 | A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire. John Bostanci, Barak Nehoran, Mark Zhandry |
| 2025 | A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities. Joey Rivkin, Gregory Valiant, Paul Valiant |
| 2025 | A New Approach for LPN-Based Pseudorandom Functions: Low-Depth and Key-Homomorphic. Youlong Ding, Aayush Jain, Ilan Komargodski |
| 2025 | A Sharp Version of Talagrand's Selector Process Conjecture and an Application to Rounding Fractional Covers. Huy Tuan Pham |
| 2025 | A Tolerant Independent Set Tester. Cameron Seth |
| 2025 | A Zero-Knowledge PCP Theorem. Tom Gur, Jack O'Connor, Nicholas Spooner |
| 2025 | Accelerated Approximate Optimization of Multi-commodity Flows on Directed Graphs. Li Chen, Andrei Graur, Aaron Sidford |
| 2025 | Adaptive Approximation Schemes for Matching Queues. Alireza AmaniHamedani, Ali Aouad, Amin Saberi |
| 2025 | Adaptive and Oblivious Statistical Adversaries Are Equivalent. Guy Blanc, Gregory Valiant |
| 2025 | Agnostic Smoothed Online Learning. Moïse Blanchard |
| 2025 | All-Pairs Shortest Paths with Few Weights per Node. Amir Abboud, Nick Fischer, Ce Jin, Virginia Vassilevska Williams, Zoe Xi |
| 2025 | Almost Optimal PAC Learning for k-Means. Vincent Cohen-Addad, Silvio Lattanzi, Chris Schwiegelshohn |
| 2025 | Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH. Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu |
| 2025 | Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time. Talya Eden, Reut Levi, Dana Ron, Ronitt Rubinfeld |
| 2025 | Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth. Zhuan Khye Koh, Omri Weinstein, Sorrachai Yingchareonthawornchai |
| 2025 | Approximation Algorithms for the Geometric Multimatching Problem. Shinwoo An, Eunjin Oh, Jie Xue |
| 2025 | Approximation Guarantees of Median Mechanism in ℝᵈ. Nikolai Gravin, Jianhao Jia |
| 2025 | Asymptotic Tensor Rank Is Characterized by Polynomials. Matthias Christandl, Koen Hoeberechts, Harold Nieuwboer, Péter Vrana, Jeroen Zuiddam |
| 2025 | Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates. Louis Golowich, Venkatesan Guruswami |
| 2025 | Asymptotically Optimal Hardness for k-Set Packing and k-Matroid Intersection. Euiwoong Lee, Ola Svensson, Theophile Thiery |
| 2025 | Better Approximation for Weighted k-Matroid Intersection. Neta Singer, Theophile Thiery |
| 2025 | Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights. Egor Gorbachev, Tomasz Kociumaka |
| 2025 | Breaking the Barrier of Self-Concordant Barriers: Faster Interior Point Methods for M-Matrices. Adrian Vladu |
| 2025 | Breaking the O(m Julia Chuzhoy, Ohad Trabelsi |
| 2025 | Breaking the Sorting Barrier for Directed Single-Source Shortest Paths. Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin |
| 2025 | Breaking the T^(2/3) Barrier for Sequential Calibration. Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich, Robert Kleinberg, Princewill Okoroafor |
| 2025 | Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics. Jason Gaitonde, Ankur Moitra, Elchanan Mossel |
| 2025 | Characterizing and Testing Principal Minor Equivalence of Matrices. Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj |
| 2025 | Classical Commitments to Quantum States. Sam Gunn, Yael Tauman Kalai, Anand Natarajan, Ági Villányi |
| 2025 | Coboundary Expansion of Coset Complexes. Tali Kaufman, Izhar Oppenheim, Shmuel Weinberger |
| 2025 | Computational Lower Bounds for No-Regret Learning in Normal-Form Games. Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm |
| 2025 | Computing Moment Polytopes of Tensors, with Applications in Algebraic Complexity and Quantum Information. Maxim van den Berg, Matthias Christandl, Vladimir Lysikov, Harold Nieuwboer, Michael Walter, Jeroen Zuiddam |
| 2025 | Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations. Yuda Feng, Yang Hu, Shi Li, Ruilong Zhang |
| 2025 | Constant Approximation of Fréchet Distance in Strongly Subquadratic Time. Siu-Wing Cheng, Haoqiang Huang, Shuo Zhang |
| 2025 | Constant Degree Networks for Almost-Everywhere Reliable Transmission. Mitali Bafna, Dor Minzer |
| 2025 | Constant-Cost Communication Is Not Reducible to k-Hamming Distance. Yuting Fang, Mika Göös, Nathaniel Harms, Pooya Hatami |
| 2025 | Constant-Factor EFX Exists for Chores. Jugal Garg, Aniket Murhekar, John Qin |
| 2025 | Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms. Sepehr Assadi, Sanjeev Khanna, Aaron Putterman |
| 2025 | Counting Random k-SAT near the Satisfiability Threshold. Zongchen Chen, Aditya Lonkar, Chunyang Wang, Kuan Yang, Yitong Yin |
| 2025 | Covering Approximate Shortest Paths with DAGs. Sepehr Assadi, Gary Hoppenworth, Nicole Wein |
| 2025 | Cryptographic Characterization of Quantum Advantage. Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa |
| 2025 | DNF Learning via Locally Mixing Random Walks. Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio |
| 2025 | Deterministic Dynamic Maximal Matching in Sublinear Update Time. Aaron Bernstein, Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak |
| 2025 | Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness. Yonggang Jiang, Chaitanya Nalam, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai |
| 2025 | Dimension Independent and Computationally Efficient Shadow Tomography. Pulkit Sinha |
| 2025 | Discrepancy Algorithms for the Binary Perceptron. Shuangping Li, Tselil Schramm, Kangjie Zhou |
| 2025 | Disjoint Connected Dominating Sets in Pseudorandom Graphs. Nemanja Draganic, Michael Krivelevich |
| 2025 | Disjoint Paths Problem with Group-Expressable Constraints. Chun-Hung Liu, Youngho Yoo |
| 2025 | Distributed Quantum Advantage for Local Problems. Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d'Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, Isadora Veeren |
| 2025 | Dynamic Locality Sensitive Orderings in Doubling Metrics. An La, Hung Le |
| 2025 | Efficient Algorithms and New Characterizations for CSP Sparsification. Sanjeev Khanna, Aaron Putterman, Madhu Sudan |
| 2025 | Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games. Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Charilaos Pipis, Jon Schneider |
| 2025 | Efficient Thermalization and Universal Quantum Computing with Quantum Gibbs Samplers. Cambyse Rouzé, Daniel Stilck França, Álvaro M. Alhambra |
| 2025 | Efficiently Finding and Counting Patterns with Distance Constraints in Sparse Graphs. Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi |
| 2025 | Entangled Mean Estimation in High Dimensions. Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, Thanasis Pittas |
| 2025 | Error-Correction of Matrix Multiplication Algorithms. Shuichi Hirahara, Nobutaka Shimizu |
| 2025 | Explicit Codes Approaching Generalized Singleton Bound using Expanders. Fernando Granha Jeronimo, Tushant Mittal, Shashank Srivastava, Madhur Tulsiani |
| 2025 | Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds. Yeyuan Chen, Zihan Zhang |
| 2025 | Explicit Two-Sided Vertex Expanders beyond the Spectral Barrier. Jun-Ting Hsieh, Ting-Chun Lin, Sidhanth Mohanty, Ryan O'Donnell, Rachel Yun Zhang |
| 2025 | Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization. Niv Buchbinder, Moran Feldman |
| 2025 | Extractors for Samplable Distributions with Low Min-Entropy. Marshall Ball, Ronen Shaltiel, Jad Silbak |
| 2025 | Fast, Robust Approximate Message Passing. Misha Ivkov, Tselil Schramm |
| 2025 | Faster Distributed Δ-Coloring via Ruling Subgraphs. Yann Bourreau, Sebastian Brandt, Alexandre Nolin |
| 2025 | Faster Lattice Basis Computation via a Natural Generalization of the Euclidean Algorithm. Kim-Manuel Klein, Janina Reuter |
| 2025 | Faster Rates for No-Regret Learning in General Games via Cautious Optimism. Ashkan Soleymani, Georgios Piliouras, Gabriele Farina |
| 2025 | Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence. Jakob Nogler, Adam Polak, Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu, Christopher Ye |
| 2025 | Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets. Albert Atserias, Iddo Tzameret |
| 2025 | Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?). Lijie Chen, Ron D. Rothblum, Roei Tell |
| 2025 | Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis. Xin Lyu, Kunal Talwar |
| 2025 | Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from #P Hardness. Dakshita Khurana, Kabir Tomer |
| 2025 | From Signaling to Interviews in Random Matching Markets. Maxwell Allman, Itai Ashlagi, Amin Saberi, Sophie H. Yu |
| 2025 | Fully Dynamic Biconnectivity in Õ(log² n) Time. Jacob Holm, Wojciech Nadara, Eva Rotenberg, Marek Sokolowski |
| 2025 | Fully Dynamic k-Median with Near-Optimal Update Time and Recourse. Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad |
| 2025 | Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions and Near-Optimal Separations. Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay, Sorrachai Yingchareonthawornchai |
| 2025 | Good Binary Quantum Codes with Transversal CCZ Gate. Quynh T. Nguyen |
| 2025 | Hardness of 4-Colouring k-Colourable Graphs. Sergey Avvakumov, Marek Filakovský, Jakub Oprsal, Gianluca Tasinato, Uli Wagner |
| 2025 | Harmonic Decomposition in Data Sketches. Dingyu Wang |
| 2025 | High Rate Multivariate Polynomial Evaluation Codes. Swastik Kopparty, Mrinal Kumar, Harry Sha |
| 2025 | History-Independent Concurrent Hash Tables. Hagit Attiya, Michael A. Bender, Martín Farach-Colton, Rotem Oshman, Noa Schiller |
| 2025 | How Random CSPs Fool Hierarchies: II. Siu On Chan, Hiu Tsun Ng |
| 2025 | How to Construct Random Unitaries. Fermi Ma, Hsin-Yuan Huang |
| 2025 | How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs. Jonathan Conroy, Arnold Filtser |
| 2025 | Hypercontractivity on HDX II: Symmetrization and q-Norms. Max Hopkins |
| 2025 | Ideal Pseudorandom Codes. Omar Alrabiah, Prabhanjan Ananth, Miranda Christ, Yevgeniy Dodis, Sam Gunn |
| 2025 | Improved Bounds for Testing Low Stabilizer Complexity States. Saeed Mehraban, Mehrdad Tahmasbi |
| 2025 | Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods. Ruichen Jiang, Aryan Mokhtari, Francisco Patitucci |
| 2025 | Improved PIR Schemes using Matching Vectors and Derivatives. Fatemeh Ghasemi, Swastik Kopparty, Madhu Sudan |
| 2025 | Leakage-Resilient Extractors against Number-on-Forehead Protocols. Eshan Chattopadhyay, Jesse Goodman |
| 2025 | Learning Quantum States Prepared by Shallow Circuits in Polynomial Time. Zeph Landau, Yunchao Liu |
| 2025 | Learning the Closest Product State. Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, Jerry Li, Allen Liu, Ryan O'Donnell, Ewin Tang |
| 2025 | Learning the Sherrington-Kirkpatrick Model Even at Low Temperature. Gautam Chandrasekaran, Adam R. Klivans |
| 2025 | Learning the Structure of Any Hamiltonian from Minimal Assumptions. Andrew Zhao |
| 2025 | Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness. Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou |
| 2025 | Lifting to Bounded-Depth and Regular Resolutions over Parities via Games. Yaroslav Alekseev, Dmitry Itsykson |
| 2025 | Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs. Hsien-Chih Chang, Jonathan Conroy, Hung Le, Shay Solomon, Cuong Than |
| 2025 | Linear Hashing Is Optimal. Michael Jaber, Vinayak M. Kumar, David Zuckerman |
| 2025 | Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More. Tuukka Korhonen |
| 2025 | List-Decoding Capacity Implies Capacity on the q-ary Symmetric Channel. Francisco Pernice, Oscar Sprumont, Mary Wootters |
| 2025 | Locality vs Quantum Codes. Samuel Dai, Ray Li |
| 2025 | Locally Sampleable Uniform Symmetric Distributions. Daniel M. Kane, Anthony Ostuni, Kewen Wu |
| 2025 | Long Arithmetic Progressions in Sumsets and Subset Sums: Constructive Proofs and Efficient Witnesses. Lin Chen, Yuchen Mao, Guochuan Zhang |
| 2025 | Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification. Josh Alman, Jingxun Liang |
| 2025 | Matrix Chaos Inequalities and Chaos of Combinatorial Type. Afonso S. Bandeira, Kevin Lucca, Petar Nizic-Nikolac, Ramon van Handel |
| 2025 | Matroid Products via Submodular Coupling. Kristóf Bérczi, Boglárka Gehér, András Imolay, László Lovász, Balázs Maga, Tamás Schwarcz |
| 2025 | Maximum Circuit Lower Bounds for Exponential-Time Arthur Merlin. Lijie Chen, Jiatu Li, Jingxun Liang |
| 2025 | Merge-Width and First-Order Model Checking. Jan Dreier, Szymon Torunczyk |
| 2025 | Metric Distortion of Small-Group Deliberation. Ashish Goel, Mohak Goyal, Kamesh Munagala |
| 2025 | Minimum Degree Edge-Disjoint Hamilton Cycles in Random Directed Graphs. Asaf Ferber, Adva Mond |
| 2025 | Model Stealing for Any Low-Rank Language Model. Allen Liu, Ankur Moitra |
| 2025 | Monotone Contractions. Eleni Batziou, John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani |
| 2025 | Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning. Deeparnab Chakrabarty, Xi Chen, Simeon Ristic, C. Seshadhri, Erik Waingarten |
| 2025 | Multi-parameter Mechanisms for Consumer Surplus Maximization. Tomer Ezra, Daniel Schoepflin, Ariel Shaulker |
| 2025 | Near Optimal Constant Inapproximability under ETH for Fundamental Problems in Parameterized Complexity. Mitali Bafna, Karthik C. S., Dor Minzer |
| 2025 | Near-Optimal Dimension Reduction for Facility Location. Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, Di Yue |
| 2025 | Near-Optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification. Sanjeev Khanna, Huan Li, Aaron Putterman |
| 2025 | Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations. Kiril Bangachev, Guy Bresler, Stefan Tiegel, Vinod Vaikuntanathan |
| 2025 | Network Unreliability in Almost-Linear Time. Ruoxu Cen, Jason Li, Debmalya Panigrahi |
| 2025 | Oblivious Defense in ML Models: Backdoor Removal without Detection. Shafi Goldwasser, Jonathan Shafer, Neekon Vafa, Vinod Vaikuntanathan |
| 2025 | Omnipredicting Single-Index Models with Multi-index Models. Lunjia Hu, Kevin Tian, Chutong Yang |
| 2025 | On Approximability of Satisfiable k-CSPs: V. Amey Bhangale, Subhash Khot, Dor Minzer |
| 2025 | On Approximability of the Permanent of PSD Matrices. Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan |
| 2025 | On Differentially Private Linear Algebra. Haim Kaplan, Yishay Mansour, Shay Moran, Uri Stemmer, Nitzan Tur |
| 2025 | On Reductions and Representations of Learning Problems in Euclidean Spaces. Bogdan Chornomaz, Shay Moran, Tom Waknine |
| 2025 | On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials IV: Linear-Length Reductions and Their Applications. Joshua A. Grochow, Youming Qiao |
| 2025 | On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials V: Over Commutative Rings. Joshua A. Grochow, Youming Qiao, Katherine E. Stange, Xiaorui Sun |
| 2025 | On the Computational Power of QAC0 with Barely Superlinear Ancillae. Anurag Anshu, Yangjing Dong, Fengning Ou, Penghui Yao |
| 2025 | On the Hardness Hierarchy for the O(n√log n) Complexity in the Word RAM. Dominik Kempa, Tomasz Kociumaka |
| 2025 | On the Limits of Language Generation: Trade-Offs between Hallucination and Mode-Collapse. Alkis Kalavasis, Anay Mehrotra, Grigoris Velegkas |
| 2025 | On the Locality of the Lovász Local Lemma. Peter Davies-Peck |
| 2025 | Online Locality Meets Distributed Quantum Computing. Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore, François Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, Václav Rozhon, Jukka Suomela |
| 2025 | Online Stochastic Matching with Unknown Arrival Order: Beating 0.5 against the Online Optimum. Enze Sun, Zhihao Gavin Tang, Yifan Wang |
| 2025 | Optimal Non-oblivious Open Addressing. Michael A. Bender, William Kuszmaul, Renfei Zhou |
| 2025 | Optimal Proof Systems for Complex Sets Are Hard to Find. Fabian Egidy, Christian Glaßer |
| 2025 | Optimal Rounding for Sparsest Cut. Alan Chang, Assaf Naor, Kevin Ren |
| 2025 | Optimal Static Dictionary with Worst-Case Constant Query Time. Yang Hu, Jingxun Liang, Huacheng Yu, Junkai Zhang, Renfei Zhou |
| 2025 | Optimality of Frequency Moment Estimation. Mark Braverman, Or Zamir |
| 2025 | Output-Sensitive Approximate Counting via a Measure-Bounded Hyperedge Oracle, or: How Asymmetry Helps Estimate k-Clique Counts Faster. Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams |
| 2025 | Parallel Repetition for 3-Player XOR Games. Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer |
| 2025 | Pauli Measurements Are Not Optimal for Single-Copy Tomography. Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, Nengkun Yu |
| 2025 | Permutation Superposition Oracles for Quantum Query Lower Bounds. Christian Majenz, Giulio Malavolta, Michael Walter |
| 2025 | Phase Transitions via Complex Extensions of Markov Chains. Jingcheng Liu, Chunyang Wang, Yitong Yin, Yixiao Yu |
| 2025 | Polynomial-Time PIT from (Almost) Necessary Assumptions. Robert Andrews, Deepanshu Kush, Roei Tell |
| 2025 | Polynomial-Time Tolerant Testing Stabilizer States. Srinivasan Arunachalam, Arkopal Dutt |
| 2025 | Positive Bias Makes Tensor-Network Contraction Tractable. Jiaqing Jiang, Jielun Chen, Norbert Schuch, Dominik Hangleiter |
| 2025 | Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals. Abhibhav Garg, Rafael Oliveira, Nitin Saxena |
| 2025 | Privately Evaluating Untrusted Black-Box Functions. Ephraim Linder, Sofya Raskhodnikova, Adam Smith, Thomas Steinke |
| 2025 | Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025 Michal Koucký, Nikhil Bansal |
| 2025 | Protecting Computations against Continuous Bounded-Communication Leakage. Yuval Ishai, Yifan Song |
| 2025 | Provably Learning a Multi-head Attention Layer. Sitan Chen, Yuanzhi Li |
| 2025 | QMA vs QCMA and Pseudorandomness. Jiahui Liu, Saachi Mutreja, Henry Yuen |
| 2025 | Quantum Advantage from Soft Decoders. André Chailloux, Jean-Pierre Tillich |
| 2025 | Quantum Communication Advantage in TFNP. Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li |
| 2025 | Quantum Fault Tolerance with Constant-Space and Logarithmic-Time Overheads. Quynh T. Nguyen, Christopher A. Pattison |
| 2025 | Quantum LDPC Codes with Transversal Non-Clifford Gates via Products of Algebraic Codes. Louis Golowich, Ting-Chun Lin |
| 2025 | Quantum One-Time Programs, Revisited. Aparna Gupte, Jiahui Liu, Justin Raizes, Bhaskar Roberts, Vinod Vaikuntanathan |
| 2025 | Quantum-Computable One-Way Functions without One-Way Functions. William Kretschmer, Luowen Qian, Avishay Tal |
| 2025 | Quasi-Linear Size PCPs with Small Soundness from HDX. Mitali Bafna, Dor Minzer, Nikhil Vyas, Zhiwei Yun |
| 2025 | Rapid Mixing at the Uniqueness Threshold. Xiaoyu Chen, Zongchen Chen, Yitong Yin, Xinyuan Zhang |
| 2025 | Reachability in One-Dimensional Pushdown Vector Addition Systems Is Decidable. Clotilde Bizière, Wojciech Czerwinski |
| 2025 | Redundancy Is All You Need. Joshua Brakensiek, Venkatesan Guruswami |
| 2025 | Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity. Simon Mackenzie, Abdallah Saffidine |
| 2025 | Rounding Large Independent Sets on Expanders. Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari |
| 2025 | Sample-Optimal Private Regression in Polynomial Time. Prashanti Anderson, Ainesh Bakshi, Mahbod Majid, Stefan Tiegel |
| 2025 | Sampling and Integration of Logconcave Functions by Algorithmic Diffusion. Yunbum Kook, Santosh S. Vempala |
| 2025 | Sandwiching Random Geometric Graphs and Erdos-Renyi with Applications: Sharp Thresholds, Robust Testing, and Enumeration. Kiril Bangachev, Guy Bresler |
| 2025 | Share-Based Fairness for Arbitrary Entitlements. Moshe Babaioff, Uriel Feige |
| 2025 | Sharp Phase Transitions in Estimation with Low-Degree Polynomials. Youngtak Sohn, Alexander S. Wein |
| 2025 | Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models. Zengfeng Huang, Zhongzheng Xiong, Xiaoyi Zhu, Zhewei Wei |
| 2025 | Simulating Time with Square-Root Space. R. Ryan Williams |
| 2025 | Single-Copy Stabilizer Testing. Marcel Hinsche, Jonas Helsen |
| 2025 | Single-Sample and Robust Online Resource Allocation. Rohan Ghuge, Sahil Singla, Yifan Wang |
| 2025 | Six Candidates Suffice to Win a Voter Majority. Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta, Kangning Wang |
| 2025 | Smoothed Analysis for Graph Isomorphism. Michael Anastos, Matthew Kwan, Benjamin R. Moore |
| 2025 | SoS Certifiability of Subgaussian Distributions and Its Algorithmic Applications. Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, Stefan Tiegel |
| 2025 | SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More. Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, Stefan Tiegel |
| 2025 | Solving the Correlation Cluster LP in Sublinear Time. Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, Hanwen Zhang |
| 2025 | Stabilizer Bootstrapping: A Recipe for Efficient Agnostic Tomography and Magic Estimation. Sitan Chen, Weiyuan Gong, Qi Ye, Zhihan Zhang |
| 2025 | Statistical Inference of a Ranked Community in a Directed Graph. Dmitriy Kunisky, Daniel A. Spielman, Alexander S. Wein, Xifan Yu |
| 2025 | Stochastic Matching via In-n-Out Local Computation Algorithms. Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Ronitt Rubinfeld |
| 2025 | Strong XOR Lemma for Information Complexity. Pachara Sawettamalya, Huacheng Yu |
| 2025 | Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap. Stefan Grosser, Marco Carmosino |
| 2025 | Subexponential Parameterized Algorithms for Hitting Subgraphs. Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi |
| 2025 | Succinct Non-interactive Arguments of Proximity. Liyan Chen, Zhengzhong Jin, Daniel Wichs |
| 2025 | Succinct Oblivious Tensor Evaluation and Applications: Adaptively-Secure Laconic Function Evaluation and Trapdoor Hashing for All Circuits. Damiano Abram, Giulio Malavolta, Lawrence Roy |
| 2025 | Sum-of-Squares Lower Bounds for Coloring Random Graphs. Aaron Potechin, Jeff Xu |
| 2025 | Supercritical Tradeoffs for Monotone Circuits. Mika Göös, Gilbert Maystre, Kilian Risse, Dmitry Sokolov |
| 2025 | Symmetric Perceptrons, Number Partitioning and Lattices. Neekon Vafa, Vinod Vaikuntanathan |
| 2025 | Tensor Concentration Inequalities: A Geometric Approach. Afonso S. Bandeira, Sivakanth Gopi, Haotian Jiang, Kevin Lucca, Thomas Rothvoss |
| 2025 | Testing Support Size More Efficiently Than Learning Histograms. Renato Ferreira Pinto Jr., Nathaniel Harms |
| 2025 | Testing and Learning Structured Quantum Hamiltonians. Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez |
| 2025 | Testing vs Estimation for Index-Invariant Properties in the Huge Object Model. Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Amit Levi, Gopinath Mishra, Sayantan Sen |
| 2025 | The 2-Token Theorem: Recognising History-Deterministic Parity Automata Efficiently. Karoliina Lehtinen, Aditya Prakash |
| 2025 | The Cost of Consistency: Submodular Maximization with Constant Recourse. Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, Morteza Zadimoghaddam |
| 2025 | The FPᴺᴾ versus #P Dichotomy for #EO. Boning Meng, Juqiu Wang, Mingji Xia |
| 2025 | The Hypergraph Removal Process. Felix Joos, Marcus Kühn |
| 2025 | The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth. Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, Katherine Van Kirk |
| 2025 | The Meta-complexity of Secret Sharing. Benny Applebaum, Oded Nir |
| 2025 | The State Hidden Subgroup Problem and an Efficient Algorithm for Locating Unentanglement. Adam Bouland, Tudor Giurgica-Tiron, John Wright |
| 2025 | The Structure of Catalytic Space: Capturing Randomness and Time via Compression. James Cook, Jiatu Li, Ian Mertz, Edward Pyne |
| 2025 | Tight Results for Online Convex Paging. Anupam Gupta, Amit Kumar, Debmalya Panigrahi |
| 2025 | Time and Space Efficient Deterministic Decoders. Joshua Cook, Dana Moshkovitz |
| 2025 | Tolerant Testing of Stabilizer States with a Polynomial Gap via a Generalized Uncertainty Relation. Zongbo Bao, Philippe van Dordrecht, Jonas Helsen |
| 2025 | Tractable Agreement Protocols. Natalie Collina, Surbhi Goel, Varun Gupta, Aaron Roth |
| 2025 | Treewidth Inapproximability and Tight ETH Lower Bound. Édouard Bonnet |
| 2025 | Truly Supercritical Trade-Offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman. Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett, Jakob Nordström, Shuo Pang |
| 2025 | Unambiguous SNARGs for P from LWE with Applications to PPAD Hardness. Liyan Chen, Cody Freitag, Zhengzhong Jin, Daniel Wichs |
| 2025 | Uncloneable Quantum States Are Necessary as Proofs and Advice. Rohit Chatterjee, Srijita Kundu, Supartha Podder |
| 2025 | Universal SNARGs for NP from Proofs of Correctness. Zhengzhong Jin, Yael Tauman Kalai, Alex Lombardi, Surya Mathialagan |
| 2025 | Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy k-LIN over Expanders. Riddhi Ghosal, Isaac M. Hair, Aayush Jain, Amit Sahai |
| 2025 | Vanishing of Schubert Coefficients. Igor Pak, Colleen Robichaux |
| 2025 | Vizing's Theorem in Near-Linear Time. Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang |
| 2025 | Weak Poincaré Inequalities, Simulated Annealing, and Sampling from Spherical Spin Glasses. Brice Huang, Sidhanth Mohanty, Amit Rajaraman, David X. Wu |
| 2025 | Weak Recovery, Hypothesis Testing, and Mutual Information in Stochastic Block Models and Planted Factor Graphs. Elchanan Mossel, Allan Sly, Youngtak Sohn |
| 2025 | When Connectivity Is Hard, Random Walks Are Easy with Non-determinism. Dean Doron, Edward Pyne, Roei Tell, R. Ryan Williams |
| 2025 | Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs. Itai Boneh, Shiri Chechik, Shay Golan, Shay Mozes, Oren Weimann |