| 2021 | On the Power of Preconditioning in Sparse Linear Regression. | Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi |
| 2021 | Embeddings of Planar Quasimetrics into Directed ℓ1 and Polylogarithmic Approximation for Directed Sparsest-Cut. | Ken-ichi Kawarabayashi, Anastasios Sidiropoulos |
| 2021 | Spectral Hypergraph Sparsifiers of Nearly Linear Size. | Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida |
| 2021 | A proof of the Erds-Faber-Lovsz conjecture: Algorithmic aspects. | Dong Yeap Kang, Tom Kelly, Daniela Khn, Abhishek Methuku, Deryk Osthus |
| 2021 | A Quantum Advantage for a Natural Streaming Problem. | John Kallaugher |
| 2021 | Sum-of-Squares Lower Bounds for Sparse Independent Set. | Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu |
| 2021 | Quantum soundness of testing tensor codes. | Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen |
| 2021 | Towards the sampling Lovsz Local Lemma. | Vishesh Jain, Huy Tuan Pham, Thuy-Duong Vuong |
| 2021 | The Minimum Formula Size Problem is (ETH) Hard. | Rahul Ilango |
| 2021 | On Worst-Case Learning in Relativized Heuristica. | Shuichi Hirahara, Mikito Nanashima |
| 2021 | Fooling Constant-Depth Threshold Circuits (Extended Abstract). | Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell |
| 2021 | Smoothed Analysis with Adaptive Adversaries. | Nika Haghtalab, Tim Roughgarden, Abhishek Shetty |
| 2021 | The zero-rate threshold for adversarial bit-deletions is less than 1/2. | Venkatesan Guruswami, Xiaoyu He, Ray Li |
| 2021 | Improved List-Decodability and List-Recoverability of Reed-Solomon Codes via Tree Packings: [Extended Abstract]. | Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters |
| 2021 | Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition. | Mohsen Ghaffari, Fabian Kuhn |
| 2021 | Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao. | Yu Gao, Yang P. Liu, Richard Peng |
| 2021 | Improved Online Correlated Selection. | Ruiquan Gao, Zhongtian He, Zhiyi Huang, Zipei Nie, Bijun Yuan, Yan Zhong |
| 2021 | Minor Sparsifiers and the Distributed Laplacian Paradigm. | Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, Mingquan Ye |
| 2021 | Integer programs with bounded subdeterminants and two nonzeros per row. | Samuel Fiorini, Gwenal Joret, Stefan Weltge, Yelena Yuditsky |
| 2021 | Hop-Constrained Metric Embeddings and their Applications. | Arnold Filtser |
| 2021 | FIXP-membership via Convex Optimization: Games, Cakes, and Markets. | Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Hgh, Alexandros Hollender |
| 2021 | List-decodability with large radius for Reed-Solomon codes. | Asaf Ferber, Matthew Kwan, Lisa Sauermann |
| 2021 | Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling. | Vitaly Feldman, Audra McMillan, Kunal Talwar |
| 2021 | Tight Bounds for General Computation in Noisy Broadcast Networks. | Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena |
| 2021 | Combinatorial Contracts. | Paul Dtting, Tomer Ezra, Michal Feldman, Thomas Kesselheim |