| 2025 | Undirected Multicast Network Coding Gaps via Locally Decodable Codes. | Mark Braverman, Zhongtian He |
| 2025 | Polynomial-Time Approximation Schemes via Utility Alignment: Unit-Demand Pricing and More. | Robin Bowers, Marius Garbea, Emmanouil Pountourakis, Samuel Taggart |
| 2025 | A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number. | Romain Bourneuf, Pierre Charbit, Stphan Thomass |
| 2025 | Exponential improvements to the average-case hardness of BosonSampling. | Adam Bouland, Ishaun Datta, Bill Fefferman, Felipe Hernandez |
| 2025 | Online Edge Coloring: Sharp Thresholds. | Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc |
| 2025 | Computational-Statistical Tradeoffs from NP-hardness. | Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan |
| 2025 | Instance-Optimal Uniformity Testing and Tracking. | Guy Blanc, Clment L. Canonne, Erik Waingarten |
| 2025 | Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices. | Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee, Xuandi Ren |
| 2025 | Deterministic factorization of constant-depth algebraic circuits in subexponential time. | Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf |
| 2025 | On Inverse Theorems and Combinatorial Lines. | Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer |
| 2025 | Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs. | Aaron Bernstein, Joakim Blikstad, Jason Li, Thatchaphol Saranurak, Ta-Wei Tu |
| 2025 | Efficiently Batching Unambiguous Interactive Proofs. | Bonnie Berger, Rohan Goyal, Matthew M. Hong, Yael Tauman Kalai |
| 2025 | Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair. | Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram, Erik Waingarten |
| 2025 | Direct Product Theorems for Randomized Query Complexity. | Shalev Ben-David, Eric Blais |
| 2025 | Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa. | Benjamin Bedert, Tamio-Vesa Nakajima, Karolina Okrasa, Stanislav Zivn |
| 2025 | Solving Linear Inequalities over the Space of Convex Sets & its Applications to Cryptography and Hydrodynamics. | Saugata Basu, Hamidreza Amini Khorasgani, Hemanta K. Maji, Hai H. Nguyen |
| 2025 | Improved Lower Bounds for all Odd-Query Locally Decodable Codes. | Arpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari, Andrew D. Lin |
| 2025 | Average Distortion Sketching. | Yiqiao Bao, Anubhav Baweja, Nicolas Menand, Erik Waingarten, Nathan White, Tian Zhang |
| 2025 | An Improved Bound for the Beck-Fiala Conjecture. | Nikhil Bansal, Haotian Jiang |
| 2025 | Optimal 4-Approximation for the Correlated Pandora's Problem. | Nikhil Bansal, Zhiyi Huang, Zixuan Zhu |
| 2025 | Factorization norms and an inverse theorem for MaxCut. | Igor Balla, Lianna Hambardzumyan, Istvn Tomon |
| 2025 | Optimal Smoothed Analysis of the Simplex Method. | Eleon Bach, Sophie Huiberts |
| 2025 | Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance. | Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein |
| 2025 | Lower Bounds for Non-adaptive Local Computation Algorithms. | Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Madhu Sudan |
| 2025 | Distributed Triangle Detection is Hard in Few Rounds. | Sepehr Assadi, Janani Sundaresan |