| 2019 | Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds. | Mohsen Ghaffari, Fabian Kuhn, Jara Uitto |
| 2019 | More Barriers for Rank Methods, via a "numeric to Symbolic" Transfer. | Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson |
| 2019 | Balancing Straight-Line Programs. | Moses Ganardi, Artur Jez, Markus Lohrey |
| 2019 | Online Matching with General Arrivals. | Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, David Wajc |
| 2019 | Polynomial Calculus Space and Resolution Width. | Nicola Galesi, Leszek Aleksander Kolodziejczyk, Neil Thapen |
| 2019 | Parametric Shortest Paths in Planar Graphs. | Kshitij Gajjar, Jaikumar Radhakrishnan |
| 2019 | Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers. | Tomer Ezra, Michal Feldman, Eric Neyman, Inbal Talgam-Cohen, S. Matthew Weinberg |
| 2019 | Polylogarithmic Guarantees for Generalized Reordering Buffer Management. | Matthias Englert, Harald Rcke, Richard Stotz |
| 2019 | Radio Network Coding Requires Logarithmic Overhead. | Klim Efremenko, Gillat Kol, Raghuvansh Saxena |
| 2019 | Learning from Outcomes: Evidence-Based Rankings. | Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona |
| 2019 | Planar Graphs have Bounded Queue-Number. | Vida Dujmovic, Gwenal Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood |
| 2019 | Laconic Conditional Disclosure of Secrets and Applications. | Nico Dttling, Sanjam Garg, Vipul Goyal, Giulio Malavolta |
| 2019 | Agreement Testing Theorems on Layered Set Systems. | Yotam Dikstein, Irit Dinur |
| 2019 | Junta Correlation is Testable. | Anindya De, Elchanan Mossel, Joe Neeman |
| 2019 | A Characterization of Graph Properties Testable for General Planar Graphs with one-Sided Error (It's all About Forbidden Subgraphs). | Artur Czumaj, Christian Sohler |
| 2019 | Modified log-Sobolev Inequalities for Strongly Log-Concave Distributions. | Mary Cryan, Heng Guo, Giorgos Mousa |
| 2019 | Tight Bounds for Online Edge Coloring. | Ilan Reuven Cohen, Binghui Peng, David Wajc |
| 2019 | Inapproximability of Clustering in Lp Metrics. | Vincent Cohen-Addad, Karthik C. S. |
| 2019 | A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs. | Vincent Cohen-Addad, Michal Pilipczuk, Marcin Pilipczuk |
| 2019 | Hardness Magnification for all Sparse NP Languages. | Lijie Chen, Ce Jin, R. Ryan Williams |
| 2019 | Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC Circuits. | Lijie Chen |
| 2019 | Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time. | Shiri Chechik, Tianyi Zhang |
| 2019 | Multi-resolution Hashing for Fast Pairwise Summations. | Moses Charikar, Paris Siminelakis |
| 2019 | Expander Graphs - Both Local and Global. | Michael Chapman, Nati Linial, Yuval Peled |
| 2019 | Faster Matroid Intersection. | Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, Sam Chiu-wai Wong |