| 2018 | Spectral Subspace Sparsification. | Huan Li, Aaron Schild |
| 2018 | Contextual Search via Intrinsic Volumes. | Renato Paes Leme, Jon Schneider |
| 2018 | Fusible HSTs and the Randomized k-Server Conjecture. | James R. Lee |
| 2018 | A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees. | Rasmus Kyng, Zhao Song |
| 2018 | Improved Decoding of Folded Reed-Solomon and Multiplicity Codes. | Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters |
| 2018 | Recharging Bandits. | Robert Kleinberg, Nicole Immorlica |
| 2018 | Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion. | Subhash Khot, Dor Minzer, Muli Safra |
| 2018 | The Sketching Complexity of Graph and Hypergraph Counting. | John Kallaugher, Michael Kapralov, Eric Price |
| 2018 | Perfect Lp Sampling in a Data Stream. | Rajesh Jayaram, David P. Woodruff |
| 2018 | 0/1/All CSPs, Half-Integral A-Path Packing, and Linear-Time FPT Algorithms. | Yoichi Iwata, Yutaro Yamaguchi, Yuichi Yoshida |
| 2018 | Epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics. | Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, Xuan Wu |
| 2018 | Simple Optimal Hitting Sets for Small-Success RL. | William Hoza, David Zuckerman |
| 2018 | Delegating Computations with (Almost) Minimal Time and Space Overhead. | Justin Holmgren, Ron Rothblum |
| 2018 | Cryptographic Hashing from Strong One-Way Functions (Or: One-Way Product Functions and Their Applications). | Justin Holmgren, Alex Lombardi |
| 2018 | Non-Black-Box Worst-Case to Average-Case Reductions within NP. | Shuichi Hirahara |
| 2018 | Knuth Prize Lecture: On the Difficulty of Approximating Boolean Max-CSPs. | Johan Hstad |
| 2018 | Computational Two-Party Correlation: A Dichotomy for Key-Agreement Protocols. | Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak |
| 2018 | Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians. | Jeongwan Haah, Matthew B. Hastings, Robin Kothari, Guang Hao Low |
| 2018 | Faster Exact and Approximate Algorithms for k-Cut. | Anupam Gupta, Euiwoong Lee, Jason Li |
| 2018 | A Faster Isomorphism Test for Graphs of Small Degree. | Martin Grohe, Daniel Neuen, Pascal Schweitzer |
| 2018 | Indistinguishability by Adaptive Procedures with Advice, and Lower Bounds on Hardness Amplification Proofs. | Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola |
| 2018 | Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. | Mika Gs, Aviad Rubinstein |
| 2018 | The Sample Complexity of Up-to-ε Multi-Dimensional Revenue Maximization. | Yannai A. Gonczarowski, S. Matthew Weinberg |
| 2018 | Counting t-Cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems. | Oded Goldreich, Guy N. Rothblum |
| 2018 | On Derandomizing Local Distributed Algorithms. | Mohsen Ghaffari, David G. Harris, Fabian Kuhn |