| 2019 | Efficient Construction of Rigid Matrices Using an NP Oracle. | Josh Alman, Lijie Chen |
| 2019 | Approximating Constraint Satisfaction Problems on High-Dimensional Expanders. | Vedat Levi Alev, Fernando Granha Jeronimo, Madhur Tulsiani |
| 2019 | Stoquastic PCP vs. Randomness. | Dorit Aharonov, Alex Bredariol Grilo |
| 2019 | Beyond the Lovsz Local Lemma: Point to Set Correlations and Their Algorithmic Applications. | Dimitris Achlioptas, Fotis Iliopoulos, Alistair Sinclair |
| 2019 | Reed-Muller Codes Polarize. | Emmanuel Abbe, Min Ye |
| 2019 | A Quantum Query Complexity Trichotomy for Regular Languages. | Scott Aaronson, Daniel Grier, Luke Schaeffer |
| 2019 | Leakage-Resilient Secret Sharing Against Colluding Parties. | Ashutosh Kumar, Raghu Meka, Amit Sahai |
| 2019 | A Deterministic Algorithm for Counting Colorings with 2-Delta Colors. | Jingcheng Liu, Alistair Sinclair, Piyush Srivastava |
| 2018 | Beating the Integrality Ratio for s-t-Tours in Graphs. | Vera Traub, Jens Vygen |
| 2018 | PPP-Completeness with Connections to Cryptography. | Katerina Sotiraki, Manolis Zampetakis, Giorgos Zirdelis |
| 2018 | Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension. | Christian Sohler, David P. Woodruff |
| 2018 | Coordinate Methods for Accelerating ℓ∞ Regression and Faster Approximate Maximum Flow. | Aaron Sidford, Kevin Tian |
| 2018 | The Diameter of the Fractional Matching Polytope and Its Hardness Implications. | Laura Sanit |
| 2018 | Near Log-Convexity of Measured Heat in (Discrete) Time and Consequences. | Mert Saglam |
| 2018 | An Improved Bound for Weak Epsilon-Nets in the Plane. | Natan Rubin |
| 2018 | Laconic Function Evaluation and Applications. | Willy Quach, Hoeteck Wee, Daniel Wichs |
| 2018 | PanORAMa: Oblivious RAM with Logarithmic Overhead. | Sarvar Patel, Giuseppe Persiano, Mariana Raykova, Kevin Yeo |
| 2018 | Hardness Magnification for Natural Problems. | Igor Carboni Oliveira, Rahul Santhanam |
| 2018 | Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA. | Anand Natarajan, Thomas Vidick |
| 2018 | Efficient Polynomial-Time Approximation Scheme for the Genus of Dense Graphs. | Bojan Mohar, Yifan Jing |
| 2018 | On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs. | Dniel Marx, Marcin Pilipczuk, Michal Pilipczuk |
| 2018 | Classical Homomorphic Encryption for Quantum Circuits. | Urmila Mahadev |
| 2018 | Classical Verification of Quantum Computations. | Urmila Mahadev |
| 2018 | MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture. | Shachar Lovett |
| 2018 | Efficiently Learning Mixtures of Mallows Models. | Allen Liu, Ankur Moitra |