| 2025 | Covering Approximate Shortest Paths with DAGs. | Sepehr Assadi, Gary Hoppenworth, Nicole Wein |
| 2025 | Vizing's Theorem in Near-Linear Time. | Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martn Costa, Shay Solomon, Tianyi Zhang |
| 2025 | Testing and Learning Structured Quantum Hamiltonians. | Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutirrez |
| 2025 | Polynomial-Time Tolerant Testing Stabilizer States. | Srinivasan Arunachalam, Arkopal Dutt |
| 2025 | The Meta-complexity of Secret Sharing. | Benny Applebaum, Oded Nir |
| 2025 | On the Computational Power of QAC0 with Barely Superlinear Ancillae. | Anurag Anshu, Yangjing Dong, Fengning Ou, Penghui Yao |
| 2025 | A Framework for Building Data Structures from Communication Protocols. | Alexandr Andoni, Shunhua Jiang, Omri Weinstein |
| 2025 | Sample-Optimal Private Regression in Polynomial Time. | Prashanti Anderson, Ainesh Bakshi, Mahbod Majid, Stefan Tiegel |
| 2025 | Smoothed Analysis for Graph Isomorphism. | Michael Anastos, Matthew Kwan, Benjamin R. Moore |
| 2025 | Computational Lower Bounds for No-Regret Learning in Normal-Form Games. | Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm |
| 2025 | Approximation Algorithms for the Geometric Multimatching Problem. | Shinwoo An, Eunjin Oh, Jie Xue |
| 2025 | Adaptive Approximation Schemes for Matching Queues. | Alireza AmaniHamedani, Ali Aouad, Amin Saberi |
| 2025 | Ideal Pseudorandom Codes. | Omar Alrabiah, Prabhanjan Ananth, Miranda Christ, Yevgeniy Dodis, Sam Gunn |
| 2025 | DNF Learning via Locally Mixing Random Walks. | Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio |
| 2025 | Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification. | Josh Alman, Jingxun Liang |
| 2025 | From Signaling to Interviews in Random Matching Markets. | Maxwell Allman, Itai Ashlagi, Amin Saberi, Sophie H. Yu |
| 2025 | Lifting to Bounded-Depth and Regular Resolutions over Parities via Games. | Yaroslav Alekseev, Dmitry Itsykson |
| 2025 | Online Locality Meets Distributed Quantum Computing. | Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore, Franois Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, Vclav Rozhon, Jukka Suomela |
| 2025 | Pauli Measurements Are Not Optimal for Single-Copy Tomography. | Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, Nengkun Yu |
| 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 | All-Pairs Shortest Paths with Few Weights per Node. | Amir Abboud, Nick Fischer, Ce Jin, Virginia Vassilevska Williams, Zoe Xi |
| 2025 | Accelerated Approximate Optimization of Multi-commodity Flows on Directed Graphs. | Li Chen, Andrei Graur, Aaron Sidford |
| 2025 | Polynomial-Time PIT from (Almost) Necessary Assumptions. | Robert Andrews, Deepanshu Kush, Roei Tell |
| 2025 | Phase Transitions via Complex Extensions of Markov Chains. | Jingcheng Liu, Chunyang Wang, Yitong Yin, Yixiao Yu |
| 2025 | Online Stochastic Matching with Unknown Arrival Order: Beating 0.5 against the Online Optimum. | Enze Sun, Zhihao Gavin Tang, Yifan Wang |