| 2017 | The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes. | Daniel Kane, Shachar Lovett, Sankeerth Rao |
| 2017 | Active Classification with Comparison Queries. | Daniel M. Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang |
| 2017 | Robust Polynomial Regression up to the Information Theoretic Limit. | Daniel Kane, Sushrut Karmalkar, Eric Price |
| 2017 | A Characterization of Testable Hypergraph Properties. | Felix Joos, Jaehoon Kim, Daniela Khn, Deryk Osthus |
| 2017 | Distributed Exact Weighted All-Pairs Shortest Paths in (n | Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak |
| 2017 | Random Formulas, Monotone Circuits, and Interpolation. | Pavel Hrubes, Pavel Pudlk |
| 2017 | Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems. | Samuel B. Hopkins, David Steurer |
| 2017 | The Power of Sum-of-Squares for Detecting Hidden Structures. | Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer |
| 2017 | Local List Recovery of High-Rate Tensor Codes & Applications. | Brett Hemenway, Noga Ron-Zewi, Mary Wootters |
| 2017 | Variable-Version Lovsz Local Lemma: Beyond Shearer's Bound. | Kun He, Liang Li, Xingwu Liu, Yuyi Wang, Mingji Xia |
| 2017 | On Small-Depth Frege Proofs for Tseitin for Grids. | Johan Hstad |
| 2017 | Lockable Obfuscation. | Rishab Goyal, Venkata Koppula, Brent Waters |
| 2017 | Query-to-Communication Lifting for BPP. | Mika Gs, Toniann Pitassi, Thomas Watson |
| 2017 | On Preparing Ground States of Gapped Hamiltonians: An Efficient Quantum Lovsz Local Lemma. | Andrs Pal Gilyn, Or Sattath |
| 2017 | Garbled Protocols and Two-Round MPC from Bilinear Maps. | Sanjam Garg, Akshayaram Srinivasan |
| 2017 | Approximating Geometric Knapsack via L-Packings. | Waldo Glvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, Andreas Wiese |
| 2017 | Random Θ(log n)-CNFs Are Hard for Cutting Planes. | Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere |
| 2017 | Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching. | Manuela Fischer, Mohsen Ghaffari, Fabian Kuhn |
| 2017 | Local Hamiltonians Whose Ground States Are Hard to Approximate. | Lior Eldar, Aram W. Harrow |
| 2017 | Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration. | Javad B. Ebrahimi, Damian Straszak, Nisheeth K. Vishnoi |
| 2017 | Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees. | David Durfee, John Peebles, Richard Peng, Anup B. Rao |
| 2017 | Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs. | Paul Duetting, Michal Feldman, Thomas Kesselheim, Brendan Lucier |
| 2017 | Oracle-Efficient Online Learning and Auction Design. | Miroslav Dudk, Nika Haghtalab, Haipeng Luo, Robert E. Schapire, Vasilis Syrgkanis, Jennifer Wortman Vaughan |
| 2017 | High Dimensional Expanders Imply Agreement Expanders. | Irit Dinur, Tali Kaufman |
| 2017 | Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures. | Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart |