| 2017 | Tight Lower Bounds for Differentially Private Selection. | Thomas Steinke, Jonathan R. Ullman |
| 2017 | Optimal Interactive Coding for Insertions, Deletions, and Substitutions. | Alexander A. Sherstov, Pei Wu |
| 2017 | Fooling Intersections of Low-Weight Halfspaces. | Rocco A. Servedio, Li-Yang Tan |
| 2017 | Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time. | Rocco A. Servedio, Li-Yang Tan |
| 2017 | Fast & Space-Efficient Approximations of Language Edit Distance and RNA Folding: An Amnesic Dynamic Programming Approach. | Barna Saha |
| 2017 | A Time-Space Lower Bound for a Large Class of Learning Problems. | Ran Raz |
| 2017 | Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice. | Yuval Peres, Alex Zhai |
| 2017 | Short Presburger Arithmetic Is Hard. | Danny Nguyen, Igor Pak |
| 2017 | An Input Sensitive Online Algorithm for the Metric Bipartite Matching Problem. | Krati Nayyar, Sharath Raghvendra |
| 2017 | Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. | Danupon Nanongkai, Thatchaphol Saranurak, Christian Wulff-Nilsen |
| 2017 | Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices. | Cameron Musco, David P. Woodruff |
| 2017 | Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space. | Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan |
| 2017 | Linear Algebraic Analogues of the Graph Isomorphism Problem and the Erdős-Rnyi Model. | Yinan Li, Youming Qiao |
| 2017 | Two-Round and Non-Interactive Concurrent Non-Malleable Commitments from Time-Lock Puzzles. | Huijia Lin, Rafael Pass, Pratik Soni |
| 2017 | Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations. | Shi Li |
| 2017 | Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion. | Yin Tat Lee, Santosh Srinivas Vempala |
| 2017 | Optimality of the Johnson-Lindenstrauss Lemma. | Kasper Green Larsen, Jelani Nelson |
| 2017 | Hardness Results for Structured Linear Systems. | Rasmus Kyng, Peng Zhang |
| 2017 | White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing. | Ilan Komargodski, Moni Naor, Eylon Yogev |
| 2017 | Learning Graphical Models Using Multiplicative Weights. | Adam R. Klivans, Raghu Meka |
| 2017 | How to Achieve Non-Malleability in One or Two Rounds. | Dakshita Khurana, Amit Sahai |
| 2017 | Polylogarithmic Approximation for Minimum Planarization (Almost). | Ken-ichi Kawarabayashi, Anastasios Sidiropoulos |
| 2017 | Faster (and Still Pretty Simple) Unbiased Estimators for Network (Un)reliability. | David R. Karger |
| 2017 | Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams. | Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh |
| 2017 | Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average. | Michael Kapralov |