| 2025 | Learning Quantum States Prepared by Shallow Circuits in Polynomial Time. | Zeph Landau, Yunchao Liu |
| 2025 | Dynamic Locality Sensitive Orderings in Doubling Metrics. | An La, Hung Le |
| 2025 | Statistical Inference of a Ranked Community in a Directed Graph. | Dmitriy Kunisky, Daniel A. Spielman, Alexander S. Wein, Xifan Yu |
| 2025 | A Bound on the Quantum Value of All Compiled Nonlocal Games. | Alexander Kulpe, Giulio Malavolta, Connor Paddock, Simon Schmidt, Michael Walter |
| 2025 | Quantum-Computable One-Way Functions without One-Way Functions. | William Kretschmer, Luowen Qian, Avishay Tal |
| 2025 | Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More. | Tuukka Korhonen |
| 2025 | High Rate Multivariate Polynomial Evaluation Codes. | Swastik Kopparty, Mrinal Kumar, Harry Sha |
| 2025 | Sampling and Integration of Logconcave Functions by Algorithmic Diffusion. | Yunbum Kook, Santosh S. Vempala |
| 2025 | Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth. | Zhuan Khye Koh, Omri Weinstein, Sorrachai Yingchareonthawornchai |
| 2025 | Faster Lattice Basis Computation via a Natural Generalization of the Euclidean Algorithm. | Kim-Manuel Klein, Janina Reuter |
| 2025 | Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from #P Hardness. | Dakshita Khurana, Kabir Tomer |
| 2025 | Efficient Algorithms and New Characterizations for CSP Sparsification. | Sanjeev Khanna, Aaron Putterman, Madhu Sudan |
| 2025 | Near-Optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification. | Sanjeev Khanna, Huan Li, Aaron Putterman |
| 2025 | On the Hardness Hierarchy for the O(n√log n) Complexity in the Word RAM. | Dominik Kempa, Tomasz Kociumaka |
| 2025 | Coboundary Expansion of Coset Complexes. | Tali Kaufman, Izhar Oppenheim, Shmuel Weinberger |
| 2025 | On Differentially Private Linear Algebra. | Haim Kaplan, Yishay Mansour, Shay Moran, Uri Stemmer, Nitzan Tur |
| 2025 | Locally Sampleable Uniform Symmetric Distributions. | Daniel M. Kane, Anthony Ostuni, Kewen Wu |
| 2025 | On the Limits of Language Generation: Trade-Offs between Hallucination and Mode-Collapse. | Alkis Kalavasis, Anay Mehrotra, Grigoris Velegkas |
| 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 Hypergraph Removal Process. | Felix Joos, Marcus Khn |
| 2025 | Universal SNARGs for NP from Proofs of Correctness. | Zhengzhong Jin, Yael Tauman Kalai, Alex Lombardi, Surya Mathialagan |
| 2025 | Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness. | Yonggang Jiang, Chaitanya Nalam, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai |
| 2025 | Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods. | Ruichen Jiang, Aryan Mokhtari, Francisco Patitucci |
| 2025 | Positive Bias Makes Tensor-Network Contraction Tractable. | Jiaqing Jiang, Jielun Chen, Norbert Schuch, Dominik Hangleiter |
| 2025 | Explicit Codes Approaching Generalized Singleton Bound using Expanders. | Fernando Granha Jeronimo, Tushant Mittal, Shashank Srivastava, Madhur Tulsiani |