| 2017 | Fast Similarity Sketching. | Sren Dahlgaard, Mathias Bk Tejs Knudsen, Mikkel Thorup |
| 2017 | Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods. | Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, Adrian Vladu |
| 2017 | On the Local Structure of Stable Clustering Instances. | Vincent Cohen-Addad, Chris Schwiegelshohn |
| 2017 | Fast and Compact Exact Distance Oracle for Planar Graphs. | Vincent Cohen-Addad, Sren Dahlgaard, Christian Wulff-Nilsen |
| 2017 | Boolean Unateness Testing with (n | Xi Chen, Erik Waingarten, Jinyu Xie |
| 2017 | Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time. | Chandra Chekuri, Kent Quanrud |
| 2017 | Hashing-Based-Estimators for Kernel Density in High Dimensions. | Moses Charikar, Paris Siminelakis |
| 2017 | A Time Hierarchy Theorem for the LOCAL Model. | Yi-Jun Chang, Seth Pettie |
| 2017 | From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. | Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan |
| 2017 | A Nearly Optimal Lower Bound on the Approximate Degree of AC | Mark Bun, Justin Thaler |
| 2017 | A Dichotomy Theorem for Nonuniform CSPs. | Andrei A. Bulatov |
| 2017 | A Dichotomy for Regular Expression Membership Testing. | Karl Bringmann, Allan Grnlund, Kasper Green Larsen |
| 2017 | A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness. | Mark Braverman, Rotem Oshman |
| 2017 | Quantum Speed-Ups for Solving Semidefinite Programs. | Fernando G. S. L. Brando, Krysta M. Svore |
| 2017 | On the Power of Statistical Zero Knowledge. | Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan |
| 2017 | Minor-Free Graphs Have Light Spanners. | Glencora Borradaile, Hung Le, Christian Wulff-Nilsen |
| 2017 | Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere. | Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani |
| 2017 | Removing Depth-Order Cycles among Triangles: An Efficient Algorithm Generating Triangular Fragments. | Mark de Berg |
| 2017 | On the Quantitative Hardness of CVP. | Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz |
| 2017 | Generalized Uniformity Testing. | Tugkan Batu, Clment L. Canonne |
| 2017 | Weighted k-Server Bounds via Combinatorial Dichotomies. | Nikhil Bansal, Marek Elis, Grigorios Koumoutsos |
| 2017 | Exponentially-Hard Gap-CSP and Local PRG via Local Hardcore Functions. | Benny Applebaum |
| 2017 | Quantum SDP-Solvers: Better Upper and Lower Bounds. | Joran van Apeldoorn, Andrs Gilyn, Sander Gribling, Ronald de Wolf |
| 2017 | Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices. | Nima Anari, Leonid Gurvits, Shayan Oveis Gharan, Amin Saberi |
| 2017 | Optimal Compression of Approximate Inner Products and Dimension Reduction. | Noga Alon, Bo'az Klartag |