| 2019 | Static data structure lower bounds imply rigidity. | Zeev Dvir, Alexander Golovnev, Omri Weinstein |
| 2019 | Fully dynamic spectral vertex sparsifiers and applications. | David Durfee, Yu Gao, Gramoz Goranci, Richard Peng |
| 2019 | Computing quartet distance is equivalent to counting 4-cycles. | Bartlomiej Dudek, Pawel Gawrychowski |
| 2019 | Capacity lower bound for the Ising perceptron. | Jian Ding, Nike Sun |
| 2019 | Degree-푑 chow parameters robustly determine degree-푑 PTFs (and algorithmic applications). | Ilias Diakonikolas, Daniel M. Kane |
| 2019 | Regression from dependent observations. | Constantinos Daskalakis, Nishanth Dikkala, Ioannis Panageas |
| 2019 | Graph pattern detection: hardness for all induced patterns and faster non-induced cycles. | Mina Dalirrooyfard, Thuy-Duong Vuong, Virginia Vassilevska Williams |
| 2019 | Distributed edge connectivity in sublinear time. | Mohit Daga, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak |
| 2019 | On approximating the covering radius and finding dense lattice subspaces. | Daniel Dadush |
| 2019 | The reachability problem for Petri nets is not elementary. | Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Jrme Leroux, Filip Mazowiecki |
| 2019 | New polynomial delay bounds for maximal subgraph enumeration by proximity search. | Alessio Conte, Takeaki Uno |
| 2019 | Solving linear programs in the current matrix multiplication time. | Michael B. Cohen, Yin Tat Lee, Zhao Song |
| 2019 | The online k-taxi problem. | Christian Coester, Elias Koutsoupias |
| 2019 | A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems. | Julia Chuzhoy, Sanjeev Khanna |
| 2019 | Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. | Arka Rai Choudhuri, Pavel Hubcek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy N. Rothblum |
| 2019 | Testing unateness nearly optimally. | Xi Chen, Erik Waingarten |
| 2019 | Bootstrapping results for threshold circuits "just beyond" known lower bounds. | Lijie Chen, Roei Tell |
| 2019 | Beyond the low-degree algorithm: mixtures of subcubes and their applications. | Sitan Chen, Ankur Moitra |
| 2019 | Parallelizing greedy for submodular set function maximization in matroids and beyond. | Chandra Chekuri, Kent Quanrud |
| 2019 | The log-approximate-rank conjecture is false. | Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif |
| 2019 | Efficient profile maximum likelihood for universal symmetric property estimation. | Moses Charikar, Kirankumar Shiragur, Aaron Sidford |
| 2019 | Almost optimal distance oracles for planar graphs. | Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann |
| 2019 | Approximation algorithms for minimum norm and ordered optimization problems. | Deeparnab Chakrabarty, Chaitanya Swamy |
| 2019 | Explicit N-vertex graphs with maximum degree K and diameter [1+o(1)] log | Michael Capalbo |
| 2019 | The structure of optimal private tests for simple hypotheses. | Clment L. Canonne, Gautam Kamath, Audra McMillan, Adam D. Smith, Jonathan R. Ullman |