| 2020 | Explicit near-Ramanujan graphs of every degree. | Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes |
| 2020 | Dynamic algorithms for LIS and distance to monotonicity. | Michael Mitzenmacher, Saeed Seddighin |
| 2020 | The impossibility of efficient quantum weak coin flipping. | Carl A. Miller |
| 2020 | The program-size complexity of self-assembled paths. | Pierre-tienne Meunier, Damien Regnault, Damien Woods |
| 2020 | Non-adaptive adaptive sampling on turnstile streams. | Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, Samson Zhou |
| 2020 | Decision list compression by mild random restrictions. | Shachar Lovett, Kewen Wu, Jiapeng Zhang |
| 2020 | An exponential time parameterized algorithm for planar disjoint paths. | Daniel Lokshtanov, Pranabendu Misra, Michal Pilipczuk, Saket Saurabh, Meirav Zehavi |
| 2020 | Lower bound for succinct range minimum query. | Mingmou Liu, Huacheng Yu |
| 2020 | Faster energy maximization for faster maximum flow. | Yang P. Liu, Aaron Sidford |
| 2020 | A polynomial lower bound on adaptive complexity of submodular maximization. | Wenzheng Li, Paul Liu, Jan Vondrk |
| 2020 | Faster parallel algorithm for approximate shortest path. | Jason Li |
| 2020 | On the computability of continuous maximum entropy distributions with applications. | Jonathan Leake, Nisheeth K. Vishnoi |
| 2020 | A spectral approach to network design. | Lap Chi Lau, Hong Zhou |
| 2020 | Three-in-a-tree in near linear time. | Kai-Yuan Lai, Hsueh-I Lu, Mikkel Thorup |
| 2020 | Strong self-concordance and sampling. | Aditi Laddha, Yin Tat Lee, Santosh S. Vempala |
| 2020 | Walking randomly, massively, and efficiently. | Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski |
| 2020 | Constant factor approximations to edit distance on far input pairs in nearly linear time. | Michal Kouck, Michael E. Saks |
| 2020 | An improved approximation algorithm for TSP in the half integral case. | Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan |
| 2020 | A phase transition and a quadratic time unbiased estimator for network reliability. | David R. Karger |
| 2020 | Separations and equivalences between turnstile streaming and linear sketching. | John Kallaugher, Eric Price |
| 2020 | Approximately stable committee selection. | Zhihao Jiang, Kamesh Munagala, Kangning Wang |
| 2020 | An improved cutting plane method for convex optimization, convex-concave games, and its applications. | Haotian Jiang, Yin Tat Lee, Zhao Song, Sam Chiu-wai Wong |
| 2020 | Positive semidefinite programming: mixed, parallel, and width-independent. | Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, Kevin Tian |
| 2020 | Implementing geometric complexity theory: on the separation of orbit closures via symmetries. | Christian Ikenmeyer, Umangathan Kandasamy |
| 2020 | Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal. | Lingxiao Huang, Nisheeth K. Vishnoi |