| 2021 | LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic. | Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor C. Oliveira |
| 2021 | Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography. | Kyle W. Burke, Matthew T. Ferland, Shang-Hua Teng |
| 2021 | Applications of Random Algebraic Constructions to Hardness of Approximation. | Boris Bukh, Karthik C. S., Bhargav Narayanan |
| 2021 | The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials. | Guy Bresler, Brice Huang |
| 2021 | An Invariance Principle for the Multi-slice, with Applications. | Mark Braverman, Subhash Khot, Noam Lifshitz, Dor Minzer |
| 2021 | Tight Space Complexity of the Coin Problem. | Mark Braverman, Sumegha Garg, Or Zamir |
| 2021 | Statistically Near-Optimal Hypothesis Selection. | Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko, Shay Moran |
| 2021 | Noise and the Frontier of Quantum Supremacy. | Adam Bouland, Bill Fefferman, Zeph Landau, Yunchao Liu |
| 2021 | Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models. | Enric Boix-Adser, Guy Bresler, Frederic Koehler |
| 2021 | Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space. | Hans L. Bodlaender, Carla Groenland, Jesper Nederlof, Cline M. F. Swennenhuis |
| 2021 | Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions. | Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu |
| 2021 | Properly learning decision trees in almost polynomial time. | Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan |
| 2021 | Multiway Online Correlated Selection. | Guy Blanc, Moses Charikar |
| 2021 | Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time. | Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak |
| 2021 | Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering. | Michael A. Bender, Bradley C. Kuszmaul, William Kuszmaul |
| 2021 | Time-Optimal Sublinear Algorithms for Matching and Vertex Cover. | Soheil Behnezhad |
| 2021 | Testability of relations between permutations. | Oren Becker, Alexander Lubotzky, Jonathan Mosheiff |
| 2021 | Harmonic Persistent Homology (extended abstract). | Saugata Basu, Nathanael Cox |
| 2021 | Unambiguous DNFs and Alon-Saks-Seymour. | Kaspars Balodis, Shalev Ben-David, Mika Gs, Siddhartha Jain, Robin Kothari |
| 2021 | Faster Sparse Minimum Cost Flow by Electrical Flow Localization. | Kyriakos Axiotis, Aleksander Madry, Adrian Vladu |
| 2021 | Quantum learning algorithms imply circuit lower bounds. | Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira, Aarthi Sundaram |
| 2021 | A Theory of PAC Learnability of Partial Concept Classes. | Noga Alon, Steve Hanneke, Ron Holzman, Shay Moran |
| 2021 | Feature Purification: How Adversarial Training Performs Robust Deep Learning. | Zeyuan Allen-Zhu, Yuanzhi Li |
| 2021 | MAJORITY-3SAT (and Related Problems) in Polynomial Time. | Shyan Akmal, Ryan Williams |
| 2021 | Covering Polygons is Even Harder. | Mikkel Abrahamsen |