| 2023 | Thin Trees for Laminar Families. | Nathan Klein, Neil Olver |
| 2023 | Slicing all Edges of an n-cube Requires n | Ohad Klein |
| 2023 | Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space. | Dominik Kempa, Tomasz Kociumaka |
| 2023 | Matrix Completion in Almost-Verification Time. | Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian |
| 2023 | Strong Bounds for 3-Progressions. | Zander Kelley, Raghu Meka |
| 2023 | Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form. | Adam Karczmarz, Piotr Sankowski |
| 2023 | Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming. | Praneeth Kacham, Rasmus Pagh, Mikkel Thorup, David P. Woodruff |
| 2023 | Directed Acyclic Outerplanar Graphs Have Constant Stack Number. | Paul Jungeblut, Laura Merker, Torsten Ueckerdt |
| 2023 | Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond. | Nathaniel Johnston, Benjamin Lovitz, Aravindan Vijayaraghavan |
| 2023 | The Complexity of Dynamic Least-Squares Regression. | Shunhua Jiang, Binghui Peng, Omri Weinstein |
| 2023 | Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error. | He Jia, Pravesh K. Kothari, Santosh S. Vempala |
| 2023 | List Decoding of Tanner and Expander Amplified Codes from Distance Certificates. | Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani |
| 2023 | Sparsifying Sums of Norms. | Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford |
| 2023 | Optimal mixing of the down-up walk on independent sets of a given size. | Vishesh Jain, Marcus Michelen, Huy Tuan Pham, Thuy-Duong Vuong |
| 2023 | SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle. | Rahul Ilango |
| 2023 | Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices. | Yao-Ching Hsieh, Huijia Lin, Ji Luo |
| 2023 | Envy-Free Cake-Cutting for Four Agents. | Alexandros Hollender, Aviad Rubinstein |
| 2023 | Learning in Pessiland via Inductive Inference. | Shuichi Hirahara, Mikito Nanashima |
| 2023 | Doubley-Efficient Interactive Proofs for Distribution Properties. | Tal Herman, Guy N. Rothblum |
| 2023 | On small-depth Frege proofs for PHP. | Johan Hstad |
| 2023 | Query-optimal estimation of unitary channels in diamond distance. | Jeongwan Haah, Robin Kothari, Ryan O'Donnell, Ewin Tang |
| 2023 | Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. | Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar |
| 2023 | Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets. | Zeyu Guo, Zihan Zhang |
| 2023 | Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting. | Ofer Grossman, Meghal Gupta, Mark Sellke |
| 2023 | Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements. | Martin Grohe, Moritz Lichter, Daniel Neuen, Pascal Schweitzer |