| 2019 | Linear-Time and Efficient Distributed Algorithms for List Coloring Graphs on Surfaces. | Luke Postle |
| 2019 | Why are Proof Complexity Lower Bounds Hard? | Jn Pich, Rahul Santhanam |
| 2019 | How to Use Heuristics for Differential Privacy. | Seth Neel, Aaron Roth, Zhiwei Steven Wu |
| 2019 | NEEXP is Contained in MIP. | Anand Natarajan, John Wright |
| 2019 | (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless. | Vasileios Nakos, Zhao Song, Zhengyu Wang |
| 2019 | Optimization of the Sherrington-Kirkpatrick Hamiltonian. | Andrea Montanari |
| 2019 | Faster Polytope Rounding, Sampling, and Volume Computation via a Sub-Linear Ball Walk. | Oren Mangoubi, Nisheeth K. Vishnoi |
| 2019 | Parallel Reachability in Almost Linear Work and Square Root Depth. | Yang P. Liu, Arun Jambulapati, Aaron Sidford |
| 2019 | Noise Sensitivity on the p -Biased Hypercube. | Noam Lifshitz, Dor Minzer |
| 2019 | Faster Minimum k-cut of a Simple Graph. | Jason Li |
| 2019 | Truly Optimal Euclidean Spanners. | Hung Le, Shay Solomon |
| 2019 | Spectral Analysis of Matrix Scaling and Operator Scaling. | Tsz Chiu Kwok, Lap Chi Lau, Akshay Ramachandran |
| 2019 | The Complexity of 3-Colouring H-Colourable Graphs. | Andrei A. Krokhin, Jakub Oprsal |
| 2019 | Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries. | Pravesh Kothari, Sahil Singla, Divyarthi Mohan, Ariel Schvartzman, S. Matthew Weinberg |
| 2019 | Efficient Truncated Statistics with Unknown Truncation. | Vasilis Kontonis, Christos Tzamos, Manolis Zampetakis |
| 2019 | The Role of Interactivity in Local Differential Privacy. | Matthew Joseph, Jieming Mao, Seth Neel, Aaron Roth |
| 2019 | Adversarial Bandits with Knapsacks. | Nicole Immorlica, Karthik Abinav Sankararaman, Robert E. Schapire, Aleksandrs Slivkins |
| 2019 | Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges. | Jacob Holm, Valerie King, Mikkel Thorup, Or Zamir, Uri Zwick |
| 2019 | Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs. | David G. Harris |
| 2019 | Optimal Document Exchange and New Codes for Insertions and Deletions. | Bernhard Haeupler |
| 2019 | Derandomization from Algebraic Hardness: Treading the Borders. | Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon |
| 2019 | Perfect Zero Knowledge for Quantum Multiprover Interactive Proofs. | Alex Bredariol Grilo, William Slofstra, Henry Yuen |
| 2019 | Non-Malleable Commitments using Goldreich-Levin List Decoding. | Vipul Goyal, Silas Richelson |
| 2019 | Sublinear Algorithms for Gap Edit Distance. | Elazar Goldenberg, Robert Krauthgamer, Barna Saha |
| 2019 | Computationally-Secure and Composable Remote State Preparation. | Alexandru Gheorghiu, Thomas Vidick |