| 2023 | (Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond. Sepehr Assadi, Janani Sundaresan |
| 2023 | A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation. Vera Traub, Rico Zenklusen |
| 2023 | A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications. Hamed Hatami, Kaave Hosseini, Xiang Meng |
| 2023 | A Characterization of List Learnability. Moses Charikar, Chirag Pabbaraju |
| 2023 | A Constant Factor Prophet Inequality for Online Combinatorial Auctions. José Correa, Andrés Cristi |
| 2023 | A Duality between One-Way Functions and Average-Case Symmetry of Information. Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira |
| 2023 | A High Dimensional Goldreich-Levin Theorem. Parker Newton, Silas Richelson, Chase Wilson |
| 2023 | A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity. Aravind Gollakota, Adam R. Klivans, Pravesh K. Kothari |
| 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 | A New Approach to Learning Linear Dynamical Systems. Ainesh Bakshi, Allen Liu, Ankur Moitra, Morris Yau |
| 2023 | A New Berry-Esseen Theorem for Expander Walks. Louis Golowich |
| 2023 | A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths. Julia Chuzhoy, Ruimin Zhang |
| 2023 | A PTAS for Minimizing Weighted Flow Time on a Single Machine. Alexander Armbruster, Lars Rohwedder, Andreas Wiese |
| 2023 | A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling. Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, Umesh V. Vazirani |
| 2023 | A Proof of the Nisan-Ronen Conjecture. George Christodoulou, Elias Koutsoupias, Annamária Kovács |
| 2023 | A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning. Ilias Diakonikolas, Christos Tzamos, Daniel M. Kane |
| 2023 | A Unified Framework for Light Spanners. Hung Le, Shay Solomon |
| 2023 | A Unifying Theory of Distance from Calibration. Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, Preetum Nakkiran |
| 2023 | Algorithmic Applications of Hypergraph and Partition Containers. Or Zamir |
| 2023 | Algorithms Approaching the Threshold for Semi-random Planted Clique. Rares-Darius Buhai, Pravesh K. Kothari, David Steurer |
| 2023 | Almost Chor-Goldreich Sources and Adversarial Random Walks. Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman |
| 2023 | Almost-Optimal Sublinear Additive Spanners. Zihan Tan, Tianyi Zhang |
| 2023 | An Analogue of Bonami's Lemma for Functions on Spaces of Linear Maps, and 2-2 Games. David Ellis, Guy Kindler, Noam Lifshitz |
| 2023 | An Efficient Decoder for a Linear Distance Quantum LDPC Code. Shouzhen Gu, Christopher A. Pattison, Eugene Tang |
| 2023 | An Improved Approximation Guarantee for Prize-Collecting TSP. Jannis Blauth, Martin Nägele |
| 2023 | An Improved Parameterized Algorithm for Treewidth. Tuukka Korhonen, Daniel Lokshtanov |
| 2023 | An Optimal "It Ain't Over Till It's Over" Theorem. Ronen Eldan, Avi Wigderson, Pei Wu |
| 2023 | Approximate Distance Sensitivity Oracles in Subquadratic Space. Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, Martin Schirneck |
| 2023 | Approximate Graph Colouring and the Hollow Shadow. Lorenzo Ciardo, Stanislav Zivný |
| 2023 | Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth. Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, Ziena Zeif |
| 2023 | Approximating Binary Longest Common Subsequence in Almost-Linear Time. Xiaoyu He, Ray Li |
| 2023 | Approximating Iterated Multiplication of Stochastic Matrices in Small Space. Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma |
| 2023 | Approximating Nash Social Welfare by Matching and Local Search. Jugal Garg, Edin Husic, Wenzheng Li, László A. Végh, Jan Vondrák |
| 2023 | Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials. Alexander S. Wein |
| 2023 | Better Trees for Santa Claus. Étienne Bamas, Lars Rohwedder |
| 2023 | Binary Error-Correcting Codes with Minimal Noiseless Feedback. Meghal Gupta, Venkatesan Guruswami, Rachel Yun Zhang |
| 2023 | Boosting Batch Arguments and RAM Delegation. Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, Daniel Wichs |
| 2023 | Capturing One-Way Functions via NP-Hardness of Meta-Complexity. Shuichi Hirahara |
| 2023 | Certified Randomness from Quantum Supremacy. Scott Aaronson, Shih-Han Hung |
| 2023 | Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification. Arun Jambulapati, Yang P. Liu, Aaron Sidford |
| 2023 | Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues. Lap Chi Lau, Kam Chuen Tung, Robert Wang |
| 2023 | Commitments to Quantum States. Sam Gunn, Nathan Ju, Fermi Ma, Mark Zhandry |
| 2023 | Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules. Xi Chen, Binghui Peng |
| 2023 | Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming. Ioannis Caragiannis, Zhile Jiang |
| 2023 | Concurrent Composition Theorems for Differential Privacy. Salil P. Vadhan, Wanrong Zhang |
| 2023 | Constant-Round Arguments from One-Way Functions. Noga Amit, Guy N. Rothblum |
| 2023 | Credible Decentralized Exchange Design via Verifiable Sequencing Rules. Matheus Venturyne Xavier Ferreira, David C. Parkes |
| 2023 | Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees. Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell |
| 2023 | Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch. Sebastian Forster, Yasamin Nazari, Maximilian Probst Gutenberg |
| 2023 | Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester. Hadley Black, Deeparnab Chakrabarty, C. Seshadhri |
| 2023 | Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE. Wei-Kai Lin, Ethan Mook, Daniel Wichs |
| 2023 | Dynamic ((1+ε) ln n)-Approximation Algorithms for Minimum Set Cover and Dominating Set. Shay Solomon, Amitai Uzrad |
| 2023 | Dynamic Maxflow via Dynamic Interior Point Methods. Jan van den Brand, Yang P. Liu, Aaron Sidford |
| 2023 | Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary Channel. Meghal Gupta, Rachel Yun Zhang |
| 2023 | Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees. Elchanan Mossel, Allan Sly, Youngtak Sohn |
| 2023 | External Memory Fully Persistent Search Trees. Gerth Stølting Brodal, Casper Moldrup Rysgaard, Rolf Svenning |
| 2023 | Extractors for Images of Varieties. Zeyu Guo, Ben Lee Volk, Akhil Jalan, David Zuckerman |
| 2023 | Fast Algorithms via Dynamic-Oracle Matroids. Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, Ta-Wei Tu |
| 2023 | Faster Deterministic Distributed MIS and Approximate Matching. Mohsen Ghaffari, Christoph Grunau |
| 2023 | Faster Isomorphism for 𝑝-Groups of Class 2 and Exponent 𝑝. Xiaorui Sun |
| 2023 | Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity. Josh Alman, Kevin Rao |
| 2023 | Finding a Small Vertex Cut on Distributed Networks. Yonggang Jiang, Sagnik Mukhopadhyay |
| 2023 | First-Order Model Checking on Structurally Sparse Graph Classes. Jan Dreier, Nikolas Mählmann, Sebastian Siebertz |
| 2023 | Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More. Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu |
| 2023 | Generic Reed-Solomon Codes Achieve List-Decoding Capacity. Joshua Brakensiek, Sivakanth Gopi, Visu Makam |
| 2023 | Good Quantum LDPC Codes with Linear Time Decoders. Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, Thomas Vidick |
| 2023 | Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness. Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai |
| 2023 | Hardness Self-Amplification: Simplified, Optimized, and Unified. Shuichi Hirahara, Nobutaka Shimizu |
| 2023 | Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis. André Lieutier, Mathijs Wintraecken |
| 2023 | Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades. Zhengyang Liu, Zeyu Ren, Zihe Wang |
| 2023 | Improved Dynamic Colouring of Sparse Graphs. Aleksander Bjørn Grodt Christiansen, Krzysztof Nowicki, Eva Rotenberg |
| 2023 | Improved and Deterministic Online Service with Deadlines or Delay. Noam Touitou |
| 2023 | Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic. Rahul Ilango, Jiatu Li, R. Ryan Williams |
| 2023 | Interior Point Methods with a Gradient Oracle. Adrian Vladu |
| 2023 | Kneser Graphs Are Hamiltonian. Arturo Merino, Torsten Mütze, Namrata |
| 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 | Learning Polynomial Transformations via Generalized Tensor Decompositions. Sitan Chen, Jerry Li, Yuanzhi Li, Anru R. Zhang |
| 2023 | Lifting Uniform Learners via Distributional Decomposition. Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan |
| 2023 | Linear Independence, Alternants, and Applications. Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich |
| 2023 | Local and Global Expansion in Random Geometric Graphs. Siqi Liu, Sidhanth Mohanty, Tselil Schramm, Elizabeth Yang |
| 2023 | Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching. Sudatta Bhattacharya, Michal Koucký |
| 2023 | Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast. Bernhard Haeupler, D. Ellis Hershkowitz, Thatchaphol Saranurak |
| 2023 | Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory. Qipeng Liu, Ran Raz, Wei Zhan |
| 2023 | Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End. Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, Fernando G. S. L. Brandão |
| 2023 | Multi-agent Contracts. Paul Dütting, Tomer Ezra, Michal Feldman, Thomas Kesselheim |
| 2023 | Multidimensional Quantum Walks. Stacey Jeffery, Sebastian Zur |
| 2023 | NLTS Hamiltonians from Good Quantum Codes. Anurag Anshu, Nikolas P. Breuckmann, Chinmay Nirkhe |
| 2023 | NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach. Yizhi Huang, Rahul Ilango, Hanlin Ren |
| 2023 | Near-Optimal Derandomization of Medium-Width Branching Programs. Aaron (Louie) Putterman, Edward Pyne |
| 2023 | Nearly All k-SAT Functions Are Unate. József Balogh, Dingding Dong, Bernard Lidický, Nitya Mani, Yufei Zhao |
| 2023 | New Algorithms for All Pairs Approximate Shortest Paths. Liam Roditty |
| 2023 | New High Dimensional Expanders from Covers. Yotam Dikstein |
| 2023 | New Subset Selection Algorithms for Low Rank Approximation: Offline and Online. David P. Woodruff, Taisuke Yasuda |
| 2023 | Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion. Ronen Eldan, Dan Mikulincer, Prasad Raghavendra |
| 2023 | Obfuscation of Pseudo-Deterministic Quantum Circuits. James Bartusek, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa |
| 2023 | On Approximability of Satisfiable k-CSPs: II. Amey Bhangale, Subhash Khot, Dor Minzer |
| 2023 | On Approximability of Satisfiable k-CSPs: III. Amey Bhangale, Subhash Khot, Dor Minzer |
| 2023 | On Regularity Lemma and Barriers in Streaming and Dynamic Matching. Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li |
| 2023 | On the Consistency of Circuit Lower Bounds for Non-deterministic Time. Albert Atserias, Sam Buss, Moritz Müller |
| 2023 | On the Optimal Fixed-Price Mechanism in Bilateral Trade. Yang Cai, Jinzhao Wu |
| 2023 | Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse. Ravishankar Krishnaswamy, Shi Li, Varun Suriyanarayana |
| 2023 | Optimal Bounds for Noisy Sorting. Yuzhou Gu, Yinzhan Xu |
| 2023 | Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization. Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer |
| 2023 | Optimal Eigenvalue Approximation via Sketching. William Swartworth, David P. Woodruff |
| 2023 | Optimal Explicit Small-Depth Formulas for the Coin Problem. Srikanth Srinivasan, Utkarsh Tripathi |
| 2023 | Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making. Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvári, Chi Jin |
| 2023 | Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme. Hu Fu, Jiawei Li, Daogao Liu |
| 2023 | Pandora's Problem with Nonobligatory Inspection: Optimal Structure and a PTAS. Hedyeh Beyhaghi, Linda Cai |
| 2023 | Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances. Václav Rozhon, Bernhard Haeupler, Anders Martinsson, Christoph Grunau, Goran Zuzic |
| 2023 | Parallel Discrete Sampling via Continuous Walks. Nima Anari, Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu, Katherine Yu |
| 2023 | Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro |
| 2023 | Planning and Learning in Partially Observable Systems via Filter Stability. Noah Golowich, Ankur Moitra, Dhruv Rohatgi |
| 2023 | Privately Estimating a Gaussian: Efficient, Robust, and Optimal. Daniel Alabi, Pravesh K. Kothari, Pranay Tankala, Prayaag Venkat, Fred Zhang |
| 2023 | Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023 Barna Saha, Rocco A. Servedio |
| 2023 | Quantum Advantage from Any Non-local Game. Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, Lisa Yang |
| 2023 | Quantum Cryptography in Algorithmica. William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal |
| 2023 | Quantum Depth in the Random Oracle Model. Atul Singh Arora, Andrea Coladangelo, Matthew Coudron, Alexandru Gheorghiu, Uttam Singh, Hendrik Waldner |
| 2023 | Quantum Free Games. Anand Natarajan, Tina Zhang |
| 2023 | Random Graph Matching at Otter's Threshold via Counting Chandeliers. Cheng Mao, Yihong Wu, Jiaming Xu, Sophie H. Yu |
| 2023 | Random Walks on Rotating Expanders. Gil Cohen, Gal Maor |
| 2023 | Randomized versus Deterministic Decision Tree Size. Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande, Jaikumar Radhakrishnan, Swagato Sanyal |
| 2023 | Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms. Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren |
| 2023 | Removing Additive Structure in 3SUM-Based Reductions. Ce Jin, Yinzhan Xu |
| 2023 | Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank. Nikhil Bansal, Haotian Jiang, Raghu Meka |
| 2023 | Robustness Implies Privacy in Statistical Estimation. Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, Shyam Narayanan |
| 2023 | SDPs and Robust Satisfiability of Promise CSP. Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep |
| 2023 | Sampling from Convex Sets with a Cold Start using Multiscale Decompositions. Hariharan Narayanan, Amit Rajaraman, Piyush Srivastava |
| 2023 | Shellability Is Hard Even for Balls. Pavel Paták, Martin Tancer |
| 2023 | Spectral Hypergraph Sparsification via Chaining. James R. Lee |
| 2023 | Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization. Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell |
| 2023 | Stochastic Minimum Vertex Cover in General Graphs: A 3/2-Approximation. Mahsa Derakhshan, Naveen Durvasula, Nika Haghtalab |
| 2023 | Streaming Euclidean MST to a Constant Factor. Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, Erik Waingarten |
| 2023 | Streaming Euclidean Max-Cut: Dimension vs Data Reduction. Xiaoyu Chen, Shaofeng H.-C. Jiang, Robert Krauthgamer |
| 2023 | Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics. Amir Abboud, Karl Bringmann, Nick Fischer |
| 2023 | Sublinear Algorithms for (1.5+ε)-Approximate Matching. Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak |
| 2023 | Sublinear Time Algorithms and Complexity of Approximate Maximum Matching. Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein |
| 2023 | Subsampling Suffices for Adaptive Data Analysis. Guy Blanc |
| 2023 | Succinct Computational Secret Sharing. Benny Applebaum, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tianren Liu, Vinod Vaikuntanathan |
| 2023 | Sum-of-Squares Lower Bounds for Densest k-Subgraph. Chris Jones, Aaron Potechin, Goutham Rajendran, Jeff Xu |
| 2023 | Testing Distributional Assumptions of Learning Algorithms. Ronitt Rubinfeld, Arsen Vasilyan |
| 2023 | The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3. Jin-Yi Cai, Ashwin Maran |
| 2023 | The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree. Marco Bressan, Matthias Lanzinger, Marc Roth |
| 2023 | The Power of Multi-step Vizing Chains. Aleksander Bjørn Grodt Christiansen |
| 2023 | The Power of Unentangled Quantum Proofs with Non-negative Amplitudes. Fernando Granha Jeronimo, Pei Wu |
| 2023 | The Randomized k-Server Conjecture Is False! Sébastien Bubeck, Christian Coester, Yuval Rabani |
| 2023 | The Rate of Interactive Codes Is Bounded Away from 1. Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena |
| 2023 | The Round Complexity of Statistical MPC with Optimal Resiliency. Benny Applebaum, Eliran Kachlon, Arpita Patra |
| 2023 | The Smoothed Complexity of Policy Iteration for Markov Decision Processes. Miranda Christ, Mihalis Yannakakis |
| 2023 | Tight Conditional Lower Bounds for Vertex Connectivity Problems. Zhiyi Huang, Yaowei Long, Thatchaphol Saranurak, Benyu Wang |
| 2023 | Towards the Erdős-Gallai Cycle Decomposition Conjecture. Matija Bucic, Richard Montgomery |
| 2023 | Uniformly Random Colourings of Sparse Graphs. Eoin Hurley, François Pirot |
| 2023 | Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic. Jiatu Li, Igor C. Oliveira |
| 2023 | Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method. Sophie Huiberts, Yin Tat Lee, Xinzhi Zhang |
| 2023 | Weighted Edit Distance Computation: Strings, Trees, and Dyck. Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha |
| 2023 | What Makes a Good Fisherman? Linear Regression under Self-Selection Bias. Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Andrew Ilyas, Manolis Zampetakis |
| 2023 | When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems. Lijie Chen, Roei Tell |