| 2023 | The Randomized k-Server Conjecture Is False! | Sbastien Bubeck, Christian Coester, Yuval Rabani |
| 2023 | External Memory Fully Persistent Search Trees. | Gerth Stlting Brodal, Casper Moldrup Rysgaard, Rolf Svenning |
| 2023 | Dynamic Maxflow via Dynamic Interior Point Methods. | Jan van den Brand, Yang P. Liu, Aaron Sidford |
| 2023 | SDPs and Robust Satisfiability of Promise CSP. | Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep |
| 2023 | Generic Reed-Solomon Codes Achieve List-Decoding Capacity. | Joshua Brakensiek, Sivakanth Gopi, Visu Makam |
| 2023 | Fast Algorithms via Dynamic-Oracle Matroids. | Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, Ta-Wei Tu |
| 2023 | An Improved Approximation Guarantee for Prize-Collecting TSP. | Jannis Blauth, Martin Ngele |
| 2023 | A Unifying Theory of Distance from Calibration. | Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, Preetum Nakkiran |
| 2023 | Lifting Uniform Learners via Distributional Decomposition. | Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan |
| 2023 | Subsampling Suffices for Adaptive Data Analysis. | Guy Blanc |
| 2023 | Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an (n√d) Monotonicity Tester. | Hadley Black, Deeparnab Chakrabarty, C. Seshadhri |
| 2023 | Approximate Distance Sensitivity Oracles in Subquadratic Space. | Davide Bil, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, Martin Schirneck |
| 2023 | Sublinear Algorithms for (1.5+ε)-Approximate Matching. | Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak |
| 2023 | Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching. | Sudatta Bhattacharya, Michal Kouck |
| 2023 | Linear Independence, Alternants, and Applications. | Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich |
| 2023 | On Approximability of Satisfiable k-CSPs: III. | Amey Bhangale, Subhash Khot, Dor Minzer |
| 2023 | On Approximability of Satisfiable k-CSPs: II. | Amey Bhangale, Subhash Khot, Dor Minzer |
| 2023 | Pandora's Problem with Nonobligatory Inspection: Optimal Structure and a PTAS. | Hedyeh Beyhaghi, Linda Cai |
| 2023 | Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ | Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, Joo Ribeiro |
| 2023 | Sublinear Time Algorithms and Complexity of Approximate Maximum Matching. | Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein |
| 2023 | Obfuscation of Pseudo-Deterministic Quantum Circuits. | James Bartusek, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa |
| 2023 | Better Trees for Santa Claus. | tienne Bamas, Lars Rohwedder |
| 2023 | Nearly All k-SAT Functions Are Unate. | Jzsef Balogh, Dingding Dong, Bernard Lidick, Nitya Mani, Yufei Zhao |
| 2023 | A New Approach to Learning Linear Dynamical Systems. | Ainesh Bakshi, Allen Liu, Ankur Moitra, Morris Yau |
| 2023 | On the Consistency of Circuit Lower Bounds for Non-deterministic Time. | Albert Atserias, Sam Buss, Moritz Mller |