| 2020 | Fully-dynamic planarity testing in polylogarithmic time. | Jacob Holm, Eva Rotenberg |
| 2020 | Non-signaling proofs with o(√ log n) provers are in PSPACE. | Dhiraj Holden, Yael Tauman Kalai |
| 2020 | Unexpected hardness results for Kolmogorov complexity under uniform reductions. | Shuichi Hirahara |
| 2020 | Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems. | Aram W. Harrow, Saeed Mehraban, Mehdi Soleimanifar |
| 2020 | New algorithms and hardness for incremental single-source shortest paths in directed graphs. | Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein |
| 2020 | Arikan meets Shannon: polar codes with near-optimal convergence to channel capacity. | Venkatesan Guruswami, Andrii Riazanov, Min Ye |
| 2020 | Optimally resilient codes for list-decoding from insertions and deletions. | Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi |
| 2020 | The Karger-Stein algorithm is optimal for k-cut. | Anupam Gupta, Euiwoong Lee, Jason Li |
| 2020 | Caching with time windows. | Anupam Gupta, Amit Kumar, Debmalya Panigrahi |
| 2020 | Interactive shallow Clifford circuits: quantum advantage against NC¹ and beyond. | Daniel Grier, Luke Schaeffer |
| 2020 | Automating cutting planes is NP-hard. | Mika Gs, Sajin Koroth, Ian Mertz, Toniann Pitassi |
| 2020 | Data structures meet cryptography: 3SUM with preprocessing. | Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, Vinod Vaikuntanathan |
| 2020 | Does preprocessing help in fast sequence comparisons? | Elazar Goldenberg, Aviad Rubinstein, Barna Saha |
| 2020 | Bare quantum simultaneity versus classical interactivity in communication complexity. | Dmitry Gavinsky |
| 2020 | Hitting topological minors is FPT. | Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi |
| 2020 | AND testing and robust judgement aggregation. | Yuval Filmus, Noam Lifshitz, Dor Minzer, Elchanan Mossel |
| 2020 | Fast sampling and counting k-SAT solutions in the local lemma regime. | Weiming Feng, Heng Guo, Yitong Yin, Chihao Zhang |
| 2020 | The one-way communication complexity of submodular maximization with applications to streaming and robustness. | Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, Rico Zenklusen |
| 2020 | Private stochastic convex optimization: optimal rates in linear time. | Vitaly Feldman, Tomer Koren, Kunal Talwar |
| 2020 | Does learning require memorization? a short tale about a long tail. | Vitaly Feldman |
| 2020 | Concentration on the Boolean hypercube via pathwise stochastic analysis. | Ronen Eldan, Renan Gross |
| 2020 | Interactive error resilience beyond 2/7. | Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena |
| 2020 | The power of factorization mechanisms in local and central differential privacy. | Alexander Edmonds, Aleksandar Nikolov, Jonathan R. Ullman |
| 2020 | Interaction is necessary for distributed learning with privacy or communication constraints. | Yuval Dagan, Vitaly Feldman |
| 2020 | A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix. | Daniel Dadush, Sophie Huiberts, Bento Natura, Lszl A. Vgh |