| 2019 | Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. | Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal |
| 2019 | A quantum-inspired classical algorithm for recommendation systems. | Ewin Tang |
| 2019 | Towards the locality of Vizing's theorem. | Hsin-Hao Su, Hoa T. Vu |
| 2019 | Local decodability of the Burrows-Wheeler transform. | Sandip Sinha, Omri Weinstein |
| 2019 | Sylvester-Gallai type theorems for quadratic polynomials. | Amir Shpilka |
| 2019 | Near-optimal lower bounds on the threshold degree and sign-rank of AC | Alexander A. Sherstov, Pei Wu |
| 2019 | Memory-sample tradeoffs for linear regression with small error. | Vatsal Sharan, Aaron Sidford, Gregory Valiant |
| 2019 | A unifying method for the design of algorithms canonizing combinatorial objects. | Pascal Schweitzer, Daniel Wiebking |
| 2019 | Oracle separation of BQP and PH. | Ran Raz, Avishay Tal |
| 2019 | On the approximation resistance of balanced linear threshold functions. | Aaron Potechin |
| 2019 | Planar point sets determine many pairwise crossing segments. | Jnos Pach, Natan Rubin, Gbor Tardos |
| 2019 | Fooling polytopes. | Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan |
| 2019 | Optimal terminal dimensionality reduction in Euclidean space. | Shyam Narayanan, Jelani Nelson |
| 2019 | Breaking quadratic time for small vertex connectivity and an approximation scheme. | Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai |
| 2019 | Stronger l | Vasileios Nakos, Zhao Song |
| 2019 | Spectral methods from tensor networks. | Ankur Moitra, Alexander S. Wein |
| 2019 | Pseudorandom generators for width-3 branching programs. | Raghu Meka, Omer Reingold, Avishay Tal |
| 2019 | Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. | Dylan M. McKay, Cody D. Murray, R. Ryan Williams |
| 2019 | Performance of Johnson-Lindenstrauss transform for | Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn |
| 2019 | Hamiltonian simulation with nearly optimal dependence on spectral norm. | Guang Hao Low |
| 2019 | DNF sparsification beyond sunflowers. | Shachar Lovett, Jiapeng Zhang |
| 2019 | Planar diameter via metric compression. | Jason Li, Merav Parter |
| 2019 | Approximation algorithms for distributionally-robust stochastic optimization with black-box distributions. | Andr Linhares, Chaitanya Swamy |
| 2019 | A fixed-depth size-hierarchy theorem for AC | Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh |
| 2019 | Flows in almost linear time via adaptive preconditioning. | Rasmus Kyng, Richard Peng, Sushant Sachdeva, Di Wang |