| 2020 | A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip. | Iftach Haitner, Yonatan Karidi-Heller |
| 2020 | Network Coding Gaps for Completion Times of Multiple Unicasts. | Bernhard Haeupler, David Wajc, Goran Zuzic |
| 2020 | Fully-Dynamic Submodular Cover with Bounded Recourse. | Anupam Gupta, Roie Levin |
| 2020 | Isomorphism Testing for Graphs Excluding Small Minors. | Martin Grohe, Daniel Wiebking, Daniel Neuen |
| 2020 | Polynomial Data Structure Lower Bounds in the Group Model. | Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein |
| 2020 | Resolving the Optimal Metric Distortion Conjecture. | Vasilis Gkatzelis, Daniel Halpern, Nisarg Shah |
| 2020 | Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes. | Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, Goutham Rajendran |
| 2020 | Independent Set on $\mathrm{P}_{k}$-Free Graphs in Quasi-Polynomial Time. | Peter Gartland, Daniel Lokshtanov |
| 2020 | Learning sums of powers of low-degree polynomials in the non-degenerate case. | Ankit Garg, Neeraj Kayal, Chandan Saha |
| 2020 | Low-Degree Hardness of Random Optimization Problems. | David Gamarnik, Aukosh Jagannath, Alexander S. Wein |
| 2020 | The complexity of approximating averages on bounded-degree graphs. | Andreas Galanis, Daniel Stefankovic, Eric Vigoda |
| 2020 | Edge-Weighted Online Bipartite Matching. | Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, Morteza Zadimoghaddam |
| 2020 | Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expanders. | Shai Evra, Tali Kaufman, Gilles Zmor |
| 2020 | Binary Interactive Error Resilience Beyond ${{}^{1}}\!/\!_{8}$ (or why $({{}^{1}}\!/\!_{2})^{3} > {{}^{1}}\!/\!_{8})$. | Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena |
| 2020 | An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions. | Paul Dtting, Thomas Kesselheim, Brendan Lucier |
| 2020 | Adjacency Labelling for Planar Graphs (and Beyond). | Vida Dujmovic, Louis Esperet, Cyril Gavoille, Gwenal Joret, Piotr Micek, Pat Morin |
| 2020 | An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature. | Andrew Drucker |
| 2020 | Sparse PCA: Algorithms, Adversarial Perturbations and Certificates. | Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer |
| 2020 | Nearly Optimal Pseudorandomness From Hardness. | Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman |
| 2020 | Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models. | Ilias Diakonikolas, Daniel M. Kane |
| 2020 | Scheduling with Communication Delays via LP Hierarchies and Clustering. | Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski, Yihao Zhang |
| 2020 | New Techniques for Proving Fine-Grained Average-Case Hardness. | Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams |
| 2020 | Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers. | Daniel Dadush, Bento Natura, Lszl A. Vgh |
| 2020 | On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs. | Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le |
| 2020 | Towards Better Approximation of Graph Crossing Number. | Julia Chuzhoy, Sepideh Mahabadi, Zihan Tan |