| 2025 | Sum-of-Squares Lower Bounds for Coloring Random Graphs. | Aaron Potechin, Jeff Xu |
| 2025 | Testing Support Size More Efficiently Than Learning Histograms. | Renato Ferreira Pinto Jr., Nathaniel Harms |
| 2025 | A Sharp Version of Talagrand's Selector Process Conjecture and an Application to Rounding Fractional Covers. | Huy Tuan Pham |
| 2025 | List-Decoding Capacity Implies Capacity on the q-ary Symmetric Channel. | Francisco Pernice, Oscar Sprumont, Mary Wootters |
| 2025 | Vanishing of Schubert Coefficients. | Igor Pak, Colleen Robichaux |
| 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 | Quantum Fault Tolerance with Constant-Space and Logarithmic-Time Overheads. | Quynh T. Nguyen, Christopher A. Pattison |
| 2025 | Good Binary Quantum Codes with Transversal CCZ Gate. | Quynh T. Nguyen |
| 2025 | Weak Recovery, Hypothesis Testing, and Mutual Information in Stochastic Block Models and Planted Factor Graphs. | Elchanan Mossel, Allan Sly, Youngtak Sohn |
| 2025 | Cryptographic Characterization of Quantum Advantage. | Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa |
| 2025 | The FPᴺᴾ versus #P Dichotomy for #EO. | Boning Meng, Juqiu Wang, Mingji Xia |
| 2025 | Improved Bounds for Testing Low Stabilizer Complexity States. | Saeed Mehraban, Mehrdad Tahmasbi |
| 2025 | Permutation Superposition Oracles for Quantum Query Lower Bounds. | Christian Majenz, Giulio Malavolta, Michael Walter |
| 2025 | How to Construct Random Unitaries. | Fermi Ma, Hsin-Yuan Huang |
| 2025 | Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity. | Simon Mackenzie, Abdallah Saffidine |
| 2025 | Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis. | Xin Lyu, Kunal Talwar |
| 2025 | Subexponential Parameterized Algorithms for Hitting Subgraphs. | Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi |
| 2025 | Efficiently Finding and Counting Patterns with Distance Constraints in Sparse Graphs. | Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi |
| 2025 | Disjoint Paths Problem with Group-Expressable Constraints. | Chun-Hung Liu, Youngho Yoo |
| 2025 | QMA vs QCMA and Pseudorandomness. | Jiahui Liu, Saachi Mutreja, Henry Yuen |
| 2025 | Model Stealing for Any Low-Rank Language Model. | Allen Liu, Ankur Moitra |
| 2025 | Discrepancy Algorithms for the Binary Perceptron. | Shuangping Li, Tselil Schramm, Kangjie Zhou |
| 2025 | Privately Evaluating Untrusted Black-Box Functions. | Ephraim Linder, Sofya Raskhodnikova, Adam Smith, Thomas Steinke |
| 2025 | The 2-Token Theorem: Recognising History-Deterministic Parity Automata Efficiently. | Karoliina Lehtinen, Aditya Prakash |
| 2025 | Asymptotically Optimal Hardness for k-Set Packing and k-Matroid Intersection. | Euiwoong Lee, Ola Svensson, Theophile Thiery |