| 2017 | 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 Chris Umans |
| 2017 | A Characterization of Testable Hypergraph Properties. Felix Joos, Jaehoon Kim, Daniela Kühn, Deryk Osthus |
| 2017 | A Dichotomy Theorem for Nonuniform CSPs. Andrei A. Bulatov |
| 2017 | A Dichotomy for Regular Expression Membership Testing. Karl Bringmann, Allan Grønlund, Kasper Green Larsen |
| 2017 | A Nearly Optimal Lower Bound on the Approximate Degree of AC Mark Bun, Justin Thaler |
| 2017 | A Proof of CSP Dichotomy Conjecture. Dmitriy Zhuk |
| 2017 | A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness. Mark Braverman, Rotem Oshman |
| 2017 | A Time Hierarchy Theorem for the LOCAL Model. Yi-Jun Chang, Seth Pettie |
| 2017 | A Time-Space Lower Bound for a Large Class of Learning Problems. Ran Raz |
| 2017 | Active Classification with Comparison Queries. Daniel M. Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang |
| 2017 | An Input Sensitive Online Algorithm for the Metric Bipartite Matching Problem. Krati Nayyar, Sharath Raghvendra |
| 2017 | Approximating Geometric Knapsack via L-Packings. Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, Andreas Wiese |
| 2017 | Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time. Chandra Chekuri, Kent Quanrud |
| 2017 | Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice. Yuval Peres, Alex Zhai |
| 2017 | Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms. Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, Justin Ward |
| 2017 | Boolean Unateness Testing with Õ(n Xi Chen, Erik Waingarten, Jinyu Xie |
| 2017 | Capacity of Neural Networks for Lifelong Learning of Composable Tasks. Leslie G. Valiant |
| 2017 | Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space. Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan |
| 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 | Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching. Manuela Fischer, Mohsen Ghaffari, Fabian Kuhn |
| 2017 | Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time. Rocco A. Servedio, Li-Yang Tan |
| 2017 | Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak |
| 2017 | Distributed PCP Theorems for Hardness of Approximation in P. Amir Abboud, Aviad Rubinstein, R. Ryan Williams |
| 2017 | Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. Danupon Nanongkai, Thatchaphol Saranurak, Christian Wulff-Nilsen |
| 2017 | Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems. Samuel B. Hopkins, David Steurer |
| 2017 | Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion. Yin Tat Lee, Santosh Srinivas Vempala |
| 2017 | Exponentially-Hard Gap-CSP and Local PRG via Local Hardcore Functions. Benny Applebaum |
| 2017 | Fast & Space-Efficient Approximations of Language Edit Distance and RNA Folding: An Amnesic Dynamic Programming Approach. Barna Saha |
| 2017 | Fast Similarity Sketching. Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Mikkel Thorup |
| 2017 | Fast and Compact Exact Distance Oracle for Planar Graphs. Vincent Cohen-Addad, Søren Dahlgaard, Christian Wulff-Nilsen |
| 2017 | Faster (and Still Pretty Simple) Unbiased Estimators for Network (Un)reliability. David R. Karger |
| 2017 | Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve. Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann |
| 2017 | First Efficient Convergence for Streaming k-PCA: A Global, Gap-Free, and Near-Optimal Rate. Zeyuan Allen-Zhu, Yuanzhi Li |
| 2017 | Fooling Intersections of Low-Weight Halfspaces. Rocco A. Servedio, Li-Yang Tan |
| 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 | Garbled Protocols and Two-Round MPC from Bilinear Maps. Sanjam Garg, Akshayaram Srinivasan |
| 2017 | Generalized Uniformity Testing. Tugkan Batu, Clément L. Canonne |
| 2017 | Hardness Results for Structured Linear Systems. Rasmus Kyng, Peng Zhang |
| 2017 | Hashing-Based-Estimators for Kernel Density in High Dimensions. Moses Charikar, Paris Siminelakis |
| 2017 | High Dimensional Expanders Imply Agreement Expanders. Irit Dinur, Tali Kaufman |
| 2017 | How to Achieve Non-Malleability in One or Two Rounds. Dakshita Khurana, Amit Sahai |
| 2017 | Learning Graphical Models Using Multiplicative Weights. Adam R. Klivans, Raghu Meka |
| 2017 | Learning Multi-Item Auctions with (or without) Samples. Yang Cai, Constantinos Daskalakis |
| 2017 | Linear Algebraic Analogues of the Graph Isomorphism Problem and the Erdős-Rényi Model. Yinan Li, Youming Qiao |
| 2017 | Local Hamiltonians Whose Ground States Are Hard to Approximate. Lior Eldar, Aram W. Harrow |
| 2017 | Local List Recovery of High-Rate Tensor Codes & Applications. Brett Hemenway, Noga Ron-Zewi, Mary Wootters |
| 2017 | Lockable Obfuscation. Rishab Goyal, Venkata Koppula, Brent Waters |
| 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 | Minor-Free Graphs Have Light Spanners. Glencora Borradaile, Hung Le, Christian Wulff-Nilsen |
| 2017 | Much Faster Algorithms for Matrix Scaling. Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson |
| 2017 | Obfuscating Compute-and-Compare Programs under LWE. Daniel Wichs, Giorgos Zirdelis |
| 2017 | On Learning Mixtures of Well-Separated Gaussians. Oded Regev, Aravindan Vijayaraghavan |
| 2017 | On Preparing Ground States of Gapped Hamiltonians: An Efficient Quantum Lovász Local Lemma. András Pal Gilyén, Or Sattath |
| 2017 | On Small-Depth Frege Proofs for Tseitin for Grids. Johan Håstad |
| 2017 | On the Local Structure of Stable Clustering Instances. Vincent Cohen-Addad, Chris Schwiegelshohn |
| 2017 | On the Power of Statistical Zero Knowledge. Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan |
| 2017 | On the Quantitative Hardness of CVP. Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz |
| 2017 | Optimal Compression of Approximate Inner Products and Dimension Reduction. Noga Alon, Bo'az Klartag |
| 2017 | Optimal Interactive Coding for Insertions, Deletions, and Substitutions. Alexander A. Sherstov, Pei Wu |
| 2017 | Optimal Las Vegas Locality Sensitive Data Structures. Thomas Dybdahl Ahle |
| 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 | Optimal Repair of Reed-Solomon Codes: Achieving the Cut-Set Bound. Itzhak Tamo, Min Ye, Alexander Barg |
| 2017 | Optimality of the Johnson-Lindenstrauss Lemma. Kasper Green Larsen, Jelani Nelson |
| 2017 | Oracle-Efficient Online Learning and Auction Design. Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E. Schapire, Vasilis Syrgkanis, Jennifer Wortman Vaughan |
| 2017 | Polylogarithmic Approximation for Minimum Planarization (Almost). Ken-ichi Kawarabayashi, Anastasios Sidiropoulos |
| 2017 | Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs. Paul Duetting, Michal Feldman, Thomas Kesselheim, Brendan Lucier |
| 2017 | Quantum SDP-Solvers: Better Upper and Lower Bounds. Joran van Apeldoorn, András Gilyén, Sander Gribling, Ronald de Wolf |
| 2017 | Quantum Speed-Ups for Solving Semidefinite Programs. Fernando G. S. L. Brandão, Krysta M. Svore |
| 2017 | Query-to-Communication Lifting for BPP. Mika Göös, Toniann Pitassi, Thomas Watson |
| 2017 | Random Formulas, Monotone Circuits, and Interpolation. Pavel Hrubes, Pavel Pudlák |
| 2017 | Random Θ(log n)-CNFs Are Hard for Cutting Planes. Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere |
| 2017 | Removing Depth-Order Cycles among Triangles: An Efficient Algorithm Generating Triangular Fragments. Mark de Berg |
| 2017 | Robust Polynomial Regression up to the Information Theoretic Limit. Daniel Kane, Sushrut Karmalkar, Eric Price |
| 2017 | Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average. Michael Kapralov |
| 2017 | Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations. Shi Li |
| 2017 | Short Presburger Arithmetic Is Hard. Danny Nguyen, Igor Pak |
| 2017 | Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices. Nima Anari, Leonid Gurvits, Shayan Oveis Gharan, Amin Saberi |
| 2017 | Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures. Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart |
| 2017 | Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration. Javad B. Ebrahimi, Damian Straszak, Nisheeth K. Vishnoi |
| 2017 | Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices. Cameron Musco, David P. Woodruff |
| 2017 | Testing Hereditary Properties of Ordered Graphs and Matrices. Noga Alon, Omri Ben-Eliezer, Eldar Fischer |
| 2017 | The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes. Daniel Kane, Shachar Lovett, Sankeerth Rao |
| 2017 | The Ising Partition Function: Zeros and Deterministic Approximation. Jingcheng Liu, Alistair Sinclair, Piyush Srivastava |
| 2017 | The Matching Problem in General Graphs Is in Quasi-NC. Ola Svensson, Jakub Tarnawski |
| 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 | Tight Lower Bounds for Differentially Private Selection. Thomas Steinke, Jonathan R. Ullman |
| 2017 | Two-Round and Non-Interactive Concurrent Non-Malleable Commitments from Time-Lock Puzzles. Huijia Lin, Rafael Pass, Pratik Soni |
| 2017 | Variable-Version Lovász Local Lemma: Beyond Shearer's Bound. Kun He, Liang Li, Xingwu Liu, Yuyi Wang, Mingji Xia |
| 2017 | Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere. Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani |
| 2017 | Weighted k-Server Bounds via Combinatorial Dichotomies. Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos |
| 2017 | White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing. Ilan Komargodski, Moni Naor, Eylon Yogev |