| 2023 | (Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond. | Sepehr Assadi, Janani Sundaresan |
| 2023 | On Regularity Lemma and Barriers in Streaming and Dynamic Matching. | Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li |
| 2023 | Quantum Depth in the Random Oracle Model. | Atul Singh Arora, Andrea Coladangelo, Matthew Coudron, Alexandru Gheorghiu, Uttam Singh, Hendrik Waldner |
| 2023 | A PTAS for Minimizing Weighted Flow Time on a Single Machine. | Alexander Armbruster, Lars Rohwedder, Andreas Wiese |
| 2023 | The Round Complexity of Statistical MPC with Optimal Resiliency. | Benny Applebaum, Eliran Kachlon, Arpita Patra |
| 2023 | Succinct Computational Secret Sharing. | Benny Applebaum, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tianren Liu, Vinod Vaikuntanathan |
| 2023 | NLTS Hamiltonians from Good Quantum Codes. | Anurag Anshu, Nikolas P. Breuckmann, Chinmay Nirkhe |
| 2023 | Parallel Discrete Sampling via Continuous Walks. | Nima Anari, Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu, Katherine Yu |
| 2023 | Constant-Round Arguments from One-Way Functions. | Noga Amit, Guy N. Rothblum |
| 2023 | A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. | Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar |
| 2023 | Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity. | Josh Alman, Kevin Rao |
| 2023 | Privately Estimating a Gaussian: Efficient, Robust, and Optimal. | Daniel Alabi, Pravesh K. Kothari, Pranay Tankala, Prayaag Venkat, Fred Zhang |
| 2023 | A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling. | Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, Umesh V. Vazirani |
| 2023 | Lattice Problems beyond Polynomial Time. | Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Alexander Golovnev, Rajendra Kumar, Zeyong Li, Spencer Peters, Noah Stephens-Davidowitz, Vinod Vaikuntanathan |
| 2023 | Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics. | Amir Abboud, Karl Bringmann, Nick Fischer |
| 2023 | Certified Randomness from Quantum Supremacy. | Scott Aaronson, Shih-Han Hung |
| 2023 | Local and Global Expansion in Random Geometric Graphs. | Siqi Liu, Sidhanth Mohanty, Tselil Schramm, Elizabeth Yang |
| 2023 | The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree. | Marco Bressan, Matthias Lanzinger, Marc Roth |
| 2023 | Optimal Explicit Small-Depth Formulas for the Coin Problem. | Srikanth Srinivasan, Utkarsh Tripathi |
| 2023 | When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems. | Lijie Chen, Roei Tell |
| 2023 | A Proof of the Nisan-Ronen Conjecture. | George Christodoulou, Elias Koutsoupias, Annamria Kovcs |
| 2023 | Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank. | Nikhil Bansal, Haotian Jiang, Raghu Meka |
| 2023 | Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth. | Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, Ziena Zeif |
| 2023 | Weighted Edit Distance Computation: Strings, Trees, and Dyck. | Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha |
| 2023 | Faster Deterministic Distributed MIS and Approximate Matching. | Mohsen Ghaffari, Christoph Grunau |