| 2019 | Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation. | Jelani Nelson, Huacheng Yu |
| 2019 | Viewing the Rings of a Tree: Minimum Distortion Embeddings into Trees. | Amir Nayyeri, Benjamin Raichel |
| 2019 | A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond. | Martin Ngele, Rico Zenklusen |
| 2019 | A Subquadratic Approximation Scheme for Partition. | Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk |
| 2019 | Seeded Graph Matching via Large Neighborhood Statistics. | Elchanan Mossel, Jiaming Xu |
| 2019 | Stochastic ℓp Load Balancing and Moment Problems via the L-Function Method. | Marco Molinaro |
| 2019 | The Complexity of the Ideal Membership Problem for Constrained Problems Over the Boolean Domain. | Monaldo Mastrolilli |
| 2019 | A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation. | Pasin Manurangsi |
| 2019 | Submodular Optimization in the MapReduce Model. | Paul Liu, Jan Vondrk |
| 2019 | Simple Concurrent Labeling Algorithms for Connected Components. | Sixue Liu, Robert E. Tarjan |
| 2019 | Short Cycles via Low-Diameter Decompositions. | Yang P. Liu, Sushant Sachdeva, Zejun Yu |
| 2019 | Can We Overcome the n log n Barrier for Oblivious Sorting? | Wei-Kai Lin, Elaine Shi, Tiancheng Xie |
| 2019 | On Facility Location with General Lower Bounds. | Shi Li |
| 2019 | A New Path from Splay to Dynamic Optimality. | Caleb C. Levy, Robert E. Tarjan |
| 2019 | A (1 + 1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists. | Chi-Kit Lam, C. Gregory Plaxton |
| 2019 | A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs. | Nathaniel Lahn, Sharath Raghvendra |
| 2019 | Efficiently Approximating Edit Distance Between Pseudorandom Strings. | William Kuszmaul |
| 2019 | Flow-Cut Gaps and Face Covers in Planar Graphs. | Robert Krauthgamer, James R. Lee, Havana Rika |
| 2019 | Simple Greedy 2-Approximation Algorithm for the Maximum Genus of a Graph. | Michal Kotrbck, Martin Skoviera |
| 2019 | Computing all Wardrop Equilibria parametrized by the Flow Demand. | Max Klimm, Philipp Warode |
| 2019 | Nearly ETH-tight algorithms for Planar Steiner Tree with Terminals on Few Faces. | Sndor Kisfaludi-Bak, Jesper Nederlof, Erik Jan van Leeuwen |
| 2019 | The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics. | Subhash Khot, Assaf Naor |
| 2019 | Optimal Construction of Compressed Indexes for Highly Repetitive Texts. | Dominik Kempa |
| 2019 | Probabilistic Tensors and Opportunistic Boolean Matrix Multiplication. | Matti Karppa, Petteri Kaski |
| 2019 | Compressed Sensing with Adversarial Sparse Noise via L1 Regression. | Sushrut Karmalkar, Eric Price |