| 2021 | Demystifying the border of depth-3 algebraic circuits. | Pranjal Dutta, Prateek Dwivedi, Nitin Saxena |
| 2021 | A time and space optimal stable population protocol solving exact majority. | David Doty, Mahsa Eftekhari, Leszek Gasieniec, Eric E. Severson, Przemyslaw Uznanski, Grzegorz Stachowiak |
| 2021 | Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR. | Itai Dinur, Nathan Keller, Ohad Klein |
| 2021 | Robust recovery for stochastic block models. | Jingqiu Ding, Tommaso d'Orsi, Rajai Nasser, David Steurer |
| 2021 | Group isomorphism is nearly-linear time for most orders. | Heiko Dietrich, James B. Wilson |
| 2021 | Hardness of Approximate Diameter: Now for Undirected Graphs. | Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams |
| 2021 | Reachability in Vector Addition Systems is Ackermann-complete. | Wojciech Czerwinski, Lukasz Orlikowski |
| 2021 | Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. | Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup |
| 2021 | Quasi-polynomial Time Approximation of Output Probabilities of Geometrically-local, Shallow Quantum Circuits. | Nolan J. Coble, Matthew Coudron |
| 2021 | Approximability of all finite CSPs with linear sketches. | Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy |
| 2021 | SNARGs for $\mathcal{P}$ from LWE. | Arka Rai Choudhuri, Abhishek Jain, Zhengzhong Jin |
| 2021 | Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier. | Alessandro Chiesa, Fermi Ma, Nicholas Spooner, Mark Zhandry |
| 2021 | On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Round. | Nai-Hui Chia, Kai-Min Chung, Qipeng Liu, Takashi Yamakawa |
| 2021 | Terminal Embeddings in Sublinear Time. | Yeshwanth Cherapanamjeri, Jelani Nelson |
| 2021 | 2-norm Flow Diffusion in Near-Linear Time. | Li Chen, Richard Peng, Di Wang |
| 2021 | Spectral Independence via Stability and Applications to Holant-Type Problems. | Zongchen Chen, Kuikui Liu, Eric Vigoda |
| 2021 | Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination. | Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau |
| 2021 | Learning Deep ReLU Networks Is Fixed-Parameter Tractable. | Sitan Chen, Adam R. Klivans, Raghu Meka |
| 2021 | Rapid mixing of Glauber dynamics via spectral independence for all degrees. | Xiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan Zhang |
| 2021 | Exponential Separations Between Learning With and Without Quantum Memory. | Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry Li |
| 2021 | Affine Extractors for Almost Logarithmic Entropy. | Eshan Chattopadhyay, Jesse Goodman, Jyun-Jie Liao |
| 2021 | Improved Extractors for Small-Space Sources. | Eshan Chattopadhyay, Jesse Goodman |
| 2021 | A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization. | Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna |
| 2021 | Minimum Cuts in Directed Graphs via Partial Sparsification. | Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Kent Quanrud |
| 2021 | Sharp Thresholds in Random Simple Temporal Graphs. | Arnaud Casteigts, Michael Raskin, Malte Renken, Viktor Zamaraev |