| 2020 | Edge Expansion and Spectral Gap of Nonnegative Matrices. | Jenish C. Mehta, Leonard J. Schulman |
| 2020 | A New Algorithm for the Robust Semi-random Independent Set Problem. | Theo McKenzie, Hermish Mehta, Luca Trevisan |
| 2020 | How to aggregate Top-lists: Approximation algorithms via scores and average ranks. | Claire Mathieu, Simon Mauras |
| 2020 | Navigating an Infinite Space with Unreliable Movements. | Anders Martinsson, Jara Uitto |
| 2020 | Tight Running Time Lower Bounds for Strong Inapproximability of Maximum | Pasin Manurangsi |
| 2020 | Parameterized Complexity and Approximability of Directed Odd Cycle Transversal. | Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi |
| 2020 | 2-Approximating Feedback Vertex Set in Tournaments. | Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan, Geevarghese Philip, Saket Saurabh |
| 2020 | Tight Bounds for the Subspace Sketch Problem with Applications. | Yi Li, Ruosong Wang, David P. Woodruff |
| 2020 | Nearly Optimal Planar | Chih-Hung Liu |
| 2020 | Detecting Feedback Vertex Sets of Size | Jason Li, Jesper Nederlof |
| 2020 | A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree. | Ray Li, Percy Liang, Stephen Mussmann |
| 2020 | A PTAS for subset TSP in minor-free graphs. | Hung Le |
| 2020 | Online Scheduling via Learned Weights. | Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, Sergei Vassilvitskii |
| 2020 | Lower Bounds for Oblivious Near-Neighbor Search. | Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo |
| 2020 | Packing LPs are Hard to Solve Accurately, Assuming Linear Equations are Hard. | Rasmus Kyng, Di Wang, Peng Zhang |
| 2020 | Achieving Optimal Backlog in the Vanilla Multi-Processor Cup Game. | William Kuszmaul |
| 2020 | Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints. | Janardhan Kulkarni, Shi Li, Jakub Tarnawski, Minwei Ye |
| 2020 | Faster Deterministic Distributed Coloring Through Recursive List Coloring. | Fabian Kuhn |
| 2020 | Ultimate greedy approximation of independent sets in subcubic graphs. | Piotr Krysta, Mathieu Mari, Nan Zhi |
| 2020 | Dominantly Truthful Multi-task Peer Prediction with a Constant Number of Tasks. | Yuqing Kong |
| 2020 | Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians. | Max Klimm, Philipp Warode |
| 2020 | Hyperbolic intersection graphs and (quasi)-polynomial time. | Sndor Kisfaludi-Bak |
| 2020 | A New Lower Bound on Hadwiger-Debrunner Numbers in the Plane. | Chaya Keller, Shakhar Smorodinsky |
| 2020 | A nearly 5/3-approximation FPT Algorithm for Min- | Ken-ichi Kawarabayashi, Bingkai Lin |
| 2020 | Simple Label-Correcting Algorithms for Partially Dynamic Approximate Shortest Paths in Directed Graphs. | Adam Karczmarz, Jakub Lacki |