| 2025 | Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings). | Lasse Wulf |
| 2025 | Root Ridge Leverage Score Sampling for ℓp Subspace Approximation. | David P. Woodruff, Taisuke Yasuda |
| 2025 | Shortest Paths on Convex Polyhedral Surfaces. | Haitao Wang |
| 2025 | Characterization of Priority-Neutral Matching Lattices. | Clayton Thomas |
| 2025 | Perfect Lp Sampling with Polylogarithmic Update Time. | William Swartworth, David P. Woodruff, Samson Zhou |
| 2025 | List Decoding Expander-Based Codes up to Capacity in Near-Linear Time. | Shashank Srivastava, Madhur Tulsiani |
| 2025 | Extractors for Samplable Distributions with Polynomially Small Min-Entropy. | Ronen Shaltiel |
| 2025 | Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses. | Mark Sellke |
| 2025 | Near-Optimal Algorithms for Omniprediction. | Princewill Okoroafor, Robert Kleinberg, Michael P. Kim |
| 2025 | Weighted k-Path and Other Problems in Almost O | Jesper Nederlof |
| 2025 | On optimal distinguishers for Planted Clique. | Ansh Nagda, Prasad Raghavendra |
| 2025 | Improved Round-by-round Soundness IOPs via Reed-Muller Codes. | Dor Minzer, Kai Zhe Zheng |
| 2025 | Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations. | Boaz Menuhin, Moni Naor |
| 2025 | Gap-preserving reductions and RE-completeness of independent set games. | Laura Mancinska, Pieter Spaas, Taro Spirig, Matthijs Vernooij |
| 2025 | Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness. | Vladimir Lysikov, Michael Walter |
| 2025 | Binary Codes for Computationally Bounded Errors Under Standard Crypto Assumptions. | George Lu, Jad Silbak, Daniel Wichs |
| 2025 | Paths and Intersections: Exact Emulators for Planar Graphs. | George Z. Li, Zihan Tan, Tianyi Zhang |
| 2025 | Adaptivity Gaps for Stochastic Probing with Subadditive Functions. | Jian Li, Yinchen Liu, Yiran Zhang |
| 2025 | Random Reed-Solomon Codes and Random Linear Codes are Locally Equivalent. | Matan Levi, Jonathan Mosheiff, Nikhil Shagrithaya |
| 2025 | Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences. | Jonathan Leake, Kasper Lindberg, Shayan Oveis Gharan |
| 2025 | Ineffectiveness for Search and Undecidability of PCSP Meta-Problems. | Alberto Larrauri |
| 2025 | Random-Shift Revisited: Tight Approximations for Tree Embeddings and ℓ₁-Oblivious Routings. | Rasmus Kyng, Maximilian Probst Gutenberg, Tim Rieder |
| 2025 | Fingerprint Filters Are Optimal. | William Kuszmaul, Jingxun Liang, Renfei Zhou |
| 2025 | Almost Tight Additive Guarantees for k-Edge-Connectivity. | Nikhil Kumar, Chaitanya Swamy |
| 2025 | The Power of Recursive Embeddings for ℓp Metrics. | Robert Krauthgamer, Nir Petruschka, Shay Sapir |