| 2021 | A (slightly) improved approximation algorithm for metric TSP. | Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan |
| 2021 | Towards tight bounds for spectral sparsification of hypergraphs. | Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida |
| 2021 | A faster algorithm for solving general LPs. | Shunhua Jiang, Zhao Song, Omri Weinstein, Hengjie Zhang |
| 2021 | Reducing isotropy and volume to KLS: an | He Jia, Aditi Laddha, Yin Tat Lee, Santosh S. Vempala |
| 2021 | Near-linear time decoding of Ta-Shma's codes via splittable regularity. | Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani |
| 2021 | SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE. | Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, Rachel Yun Zhang |
| 2021 | Vertex deletion parameterized by elimination distance and even less. | Bart M. P. Jansen, Jari J. H. de Kroon, Michal Wlodarczyk |
| 2021 | Perfectly sampling | Vishesh Jain, Ashwin Sah, Mehtaab Sawhney |
| 2021 | Indistinguishability obfuscation from well-founded assumptions. | Aayush Jain, Huijia Lin, Amit Sahai |
| 2021 | Neural tangent kernel: convergence and generalization in neural networks (invited paper). | Arthur Jacot, Franck Gabriel, Clment Hongler |
| 2021 | Online stochastic matching, poisson arrivals, and the natural linear program. | Zhiyi Huang, Xinkai Shu |
| 2021 | Fiat-Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge). | Justin Holmgren, Alex Lombardi, Ron D. Rothblum |
| 2021 | Average-case hardness of NP from exponential worst-case hardness assumptions. | Shuichi Hirahara |
| 2021 | On codes decoding a constant fraction of errors on the BSC. | Jan Hazla, Alex Samorodnitsky, Ori Sberlo |
| 2021 | Fiber bundle codes: breaking the | Matthew B. Hastings, Jeongwan Haah, Ryan O'Donnell |
| 2021 | Efficient randomized distributed coloring in CONGEST. | Magns M. Halldrsson, Fabian Kuhn, Yannic Maus, Tigran Tonoyan |
| 2021 | Universally-optimal distributed algorithms for known topologies. | Bernhard Haeupler, David Wajc, Goran Zuzic |
| 2021 | Tree embeddings for hop-constrained network design. | Bernhard Haeupler, D. Ellis Hershkowitz, Goran Zuzic |
| 2021 | Capacity lower bounds via productization. | Leonid Gurvits, Jonathan Leake |
| 2021 | Efficient list-decoding with constant alphabet and list sizes. | Zeyu Guo, Noga Ron-Zewi |
| 2021 | Load balancing guardrails: keeping your heavy traffic on the road to low response times (invited paper). | Isaac Grosof, Ziv Scully, Mor Harchol-Balter |
| 2021 | (Sub)Exponential advantage of adiabatic Quantum computation with no sign problem. | Andrs Gilyn, Matthew B. Hastings, Umesh V. Vazirani |
| 2021 | Efficient randomized DCAS. | George Giakkoupis, Mehrdad Jafari Giv, Philipp Woelfel |
| 2021 | Hardness of learning DNFs using halfspaces. | Suprovat Ghoshal, Rishi Saket |
| 2021 | Sample-efficient proper PAC learning with approximate differential privacy. | Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi |