| 2025 | Collapsing Catalytic Classes. | Michal Kouck, Ian Mertz, Edward Pyne, Sasha Sami |
| 2025 | Overcomplete Tensor Decomposition via Koszul-Young Flattenings. | Pravesh K. Kothari, Ankur Moitra, Alexander S. Wein |
| 2025 | Stronger Cell Probe Lower Bounds via Local PRGs. | Oliver Korten, Toniann Pitassi, Russell Impagliazzo |
| 2025 | Dynamic Treewidth in Logarithmic Time. | Tuukka Korhonen |
| 2025 | Faster Logconcave Sampling from a Cold Start in High Dimension. | Yunbum Kook, Santosh S. Vempala |
| 2025 | Density Measures for Language Generation. | Jon M. Kleinberg, Fan Wei |
| 2025 | Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching. | Seri Khoury, Aaron Schild |
| 2025 | A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams. | Sanjeev Khanna, Ashwin Padaki, Krish Singal, Erik Waingarten |
| 2025 | On the Parallel Complexity of Finding a Matroid Basis. | Sanjeev Khanna, Aaron Putterman, Junkai Song |
| 2025 | Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives. | Thomas Kesselheim, Marco Molinaro, Kalen Patton, Sahil Singla |
| 2025 | More efficient sifting for grid norms, and applications to multiparty communication complexity. | Zander Kelley, Xin Lyu |
| 2025 | Solving Zero-Sum Games with Fewer Matrix-Vector Products. | Ishani Karmarkar, Liam O'Carroll, Aaron Sidford |
| 2025 | Maximally Extendable Product Codes are Good Coboundary Expanders. | Gleb Kalachev, Pavel Panteleev |
| 2025 | Near-Optimal Property Testers for Pattern Matching. | Ce Jin, Tomasz Kociumaka |
| 2025 | Generalized Flow in Nearly-linear Time on Moderately Dense Graphs. | Shunhua Jiang, Michael Kapralov, Lawrence Li, Aaron Sidford |
| 2025 | A k | Oliver Janzer, Peter Manohar |
| 2025 | Radial Isotropic Position via an Implicit Newton's Method. | Arun Jambulapati, Jonathan Li, Kevin Tian |
| 2025 | On Succinct Obfuscation via Propositional Proofs. | Abhishek Jain, Zhengzhong Jin, Surya Mathialagan, Omer Paneth |
| 2025 | Quasipolynomial Bounds for the Corners Theorem. | Michael Jaber, Yang P. Liu, Shachar Lovett, Anthony Ostuni, Mehtaab Sawhney |
| 2025 | Succinct Homomorphic MACs from Groups and Applications. | Yuval Ishai, Hanjun Li, Huijia Lin |
| 2025 | Cryptography Meets Worst-case Complexity: Optimal Security and More From iO and Worst-case Assumptions. | Rahul Ilango, Alex Lombardi |
| 2025 | Gdel in Cryptography: Effectively Zero-Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness. | Rahul Ilango |
| 2025 | Static Retrieval Revisited: To Optimality and Beyond. | Yang Hu, William Kuszmaul, Jingxun Liang, Huacheng Yu, Junkai Zhang, Renfei Zhou |
| 2025 | Obfuscation of Unitary Quantum Programs. | Mi-Ying (Miryam) Huang, Er-Cheng Tang |
| 2025 | Edge-weighted Matching in the Dark. | Zhiyi Huang, Enze Sun, Xiaowei Wu, Jiahao Zhao |