FOCS 2017 accepted papers

• Ilias Diakonikolas, Daniel Kane and Alistair Stewart. Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures
• Mark de Berg. Removing Depth-Order Cycles Among Triangles: An Efficient Algorithm Generating Triangular Fragments
• Pavel Pudlak and Pavel Hrubes. Random formulas, monotone circuits, and interpolation
• Noah Fleming, Denis Pankratov, Toniann Pitassi and Robert Robere. Random CNFs are Hard for Cutting Planes
• Felix Joos, Jaehoon Kim, Daniela Kühn and Deryk Osthus. A characterization of testable hypergraph properties
• Daniel Kane, Shachar Lovett and Sankeerth Rao. The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes
• Kasper Green Larsen and Jelani Nelson. Optimality of the Johnson-Lindenstrauss lemma
• Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff and Mobin Yahyazadeh. Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams
• Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler and Prashant Vasudevan. On The Power of Statistical Zero Knowledge
• Noga Alon and Bo'Az Klartag. Optimal compression of approximate inner products and dimension reduction
• Yin Tat Lee and Santosh Vempala. Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion
• Danny Nguyen and Igor Pak. Short Presburger arithmetic is hard
• Johan Hastad. On small-depth Frege proofs for Tseitin for graphs
• Mark Bun and Justin Thaler. A Nearly Optimal Lower Bound on the Approximate Degree of AC^0
• Dakshita Khurana and Amit Sahai. How to Achieve Non-Malleability in One or Two Rounds
• Jingcheng Liu, Alistair Sinclair and Piyush Srivastava. The Ising Partition Function: Zeros and Deterministic Approximation
• Glencora Borradaile, Hung Le and Christian Wulff-Nilsen. Minor-free graphs have light spanners
• Karl Bringmann, Allan Grønlund and Kasper Green Larsen. A Dichotomy for Regular Expression Membership Testing
• Vincent Cohen-Addad, Søren Dahlgaard and Christian Wulff-Nilsen. Fast and Compact Exact Distance Oracle for Planar Graphs
• Ola Svensson and Jakub Tarnawski. The Matching Problem in General Graphs is in Quasi-NC
• Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson and Justin Ward. Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms
• Rocco Servedio and Li-Yang Tan. Deterministic search for CNF satisfying assignments in almost polynomial time
• Rocco Servedio and Li-Yang Tan. Fooling intersections of low-weight halfspaces
• Shi Li. Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations
• Yinan Li and Youming Qiao. Linear algebraic analogues of the graph isomorphism problem and the Erdős–Rényi model
• Chandra Chekuri and Kent Quanrud. Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time
• Andrei Bulatov. A dichotomy theorem for nonuniform CSPs
• Dmitriy Zhuk. The Proof of CSP Dichotomy Conjecture
• Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee and Madhur Tulsiani. Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere
• Yuval Peres and Alex Zhai. Average-case reconstruction for the deletion channel: subpolynomially many traces suffice
• Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira and Avi Wigderson. Much Faster Algorithms for Matrix Scaling
• Michael B. Cohen, Aleksander Mądry, Dimitris Tsipras and Adrian Vladu. Matrix Scaling and Balancing via Box Constrained Newton’s Method and Interior Point Methods
• Alexander Sherstov and Pei Wu. Optimal Interactive Coding for Insertions, Deletions, and Substitutions
• Huck Bennett, Alexander Golovnev and Noah Stephens-Davidowitz. On the Quantitative Hardness of CVP
• Noga Alon, Omri Ben-Eliezer and Eldar Fischer. Testing Hereditary Properties of Ordered Graphs and Matrices
• Vincent Cohen-Addad and Chris Schwiegelshohn. On the Local Structure of Stable Clustering Instances
• Javad B. Ebrahimi, Damian Straszak and Nisheeth K. Vishnoi. Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration
• Brett Hemenway, Noga Ron-Zewi and Mary Wootters. Local List Recovery of High-rate Tensor Codes & Applications
• Irit Dinur and Tali Kaufman. High dimensional expanders are agreement expanders
• Thomas Steinke and Jonathan Ullman. Tight Lower Bounds for Differentially Private Selection
• Ran Raz. A Time-Space Lower Bound for a Large Class of Learning Problems
• Manuela Fischer, Mohsen Ghaffari and Fabian Kuhn. Deterministic Distributed Edge Coloring via Hypergraph Maximal Matching
• Fernando Brandao and Krysta Svore. Quantum Speed-ups for Semidefinite Programming
• Joran van Apeldoorn, Andras Gilyen, Sander Gribling and Ronald de Wolf. Quantum SDP-Solvers: Better upper and lower bounds
• Chien-Chung Huang, Danupon Nanongkai and Thatchaphol Saranurak. Distributed Exact Weighted All-Pairs Shortest Paths in $\tilde O(n^{5/4})$ Rounds
• Danupon Nanongkai, Thatchaphol Saranurak and Christian Wulff-Nilsen. Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time
• Mark Braverman and Rotem Oshman. A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness
• Cameron Musco and David P. Woodruff. Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices
• Søren Dahlgaard, Mathias Bæk Tejs Knudsen and Mikkel Thorup. Fast Similarity Sketching
• Rishab Goyal, Venkata Koppula and Brent Waters. Lockable Obfuscation
• Daniel Wichs and Giorgos Zirdelis. Obfuscating Compute-and-Compare Programs under LWE
• Nikhil Bansal, Marek Elias and Grigorios Koumoutsos. Weighted k-Server Bounds via Combinatorial Dichotomies
• Moni Naor, Ilan Komargodski and Eylon Yogev. White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing
• Mika Göös, Toniann Pitassi and Thomas Watson. Query-to-Communication Lifting for BPP
• Oded Regev and Aravindan Vijayaraghavan. On Learning Mixtures of Well-Separated Gaussians
• Sanjam Garg and Akshayaram Srinivasan. Garbled Protocols and Two-Round MPC from Bilinear Maps
• Xi Chen, Erik Waingarten and Jinyu Xie. Boolean Unateness Testing with ~O(n^{3/4}) Adaptive Queries
• Benny Applebaum. Exponentially Hard gap-CSP and local PRG via Local Hardcore Functions
• Waldo Galvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan and Andreas Wiese. Approximating Geometric Knapsack via L-packings
• Paul Duetting, Michal Feldman, Thomas Kesselheim and Brendan Lucier. Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs
• Itzhak Tamo, Min Ye and Alexander Barg. Optimal repair of Reed-Solomon codes: Achieving the cut-set bound
• David Karger. A Recursive Contraction Algorithm \\for Network (Un)reliability
• Michael Kapralov. Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average
• Amir Abboud, Aviad Rubinstein and Ryan Williams. Distributed PCP Theorems for Hardness of Approximation in P
• Barna Saha. Fast & Space-Efficient Approximations of Language Edit Distance and RNA-Folding: An Amnesic Dynamic Programming Approach
• Zeyuan Allen-Zhu and Yuanzhi Li. Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate
• Daniel Kane, Shachar Lovett, Shay Moran and Jiapeng Zhang. Active classification with comparison queries
• Miroslav Dudik, Nika Haghtalab, Haipeng Luo, Robert E. Schapire, Vasilis Syrgkanis and Jennifer Wortman Vaughan. Oracle-Efficient Online Learning and Auction Design
• Adam Klivans and Raghu Meka. Learning Graphical Models Using Multiplicative Weights
• Samuel Hopkins and David Steurer. Efficient Bayesian estimation from few samples: community detection and related problems
• Jack Murtagh, Omer Reingold, Aaron Sidford and Salil Vadhan. Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
• David Durfee, John Peebles, Richard Peng and Anup B. Rao. Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees
• Leslie Valiant. Capacity of Neural Networks for Lifelong Learning of Composable Tasks
• Andras Pal Gilyen and Or Sattath. On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma
• Amir Abboud, Arturs Backurs, Karl Bringmann and Marvin Kunnemann. Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve
• Yang Cai and Constantinos Daskalakis. Learning Multi-item Auctions with (and without) Samples
• Nima Anari, Leonid Gurvits, Shayan Oveis Gharan and Amin Saberi. Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices
• Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai and Luca Trevisan. From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
• Thomas Dybdahl Ahle. Optimal Las Vegas Locality Sensitive Data Structures
• Ken-Ichi Kawarabayashi and Anastasios Sidiropoulos. Polylogarithmic approximation for minimum planarization (almost)
• Yi-Jun Chang and Seth Pettie. A Time Hierarchy Theorem for the LOCAL Model
• Kun He, Liang Li, Xingwu Liu, Yuyi Wang and Mingji Xia. Variable Version Lov\'{a}sz Local Lemma: Beyond Shearer's Bound
• Rasmus Kyng and Peng Zhang. Hardness Results for Structured Linear Systems
• Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm and David Steurer. The Power of Sum-of-Squares for Detecting Hidden Structures
• Moses Charikar and Paris Siminelakis. Hashing-Based-Estimators for Kernel Density in High Dimensions
• Huijia Lin, Rafael Pass and Pratik Soni. Two-Round and Non-interactive Concurrent Non-Malleable Commitments from Time-Lock Puzzles
• Krati Nayyar and Sharath Raghvendra. A Metric Sensitive Online Algorithm for Minimum Bipartite Matching
• Lior Eldar and Aram Harrow. Local Hamiltonians Whose Ground States are Hard to Approximate
• Daniel Kane, Sushrut Karmalkar and Eric Price. Robust polynomial regression up to the information theoretic limit
• Tugkan Batu and Clément Canonne. Generalized Uniformity Testing

90 papers accepted out of 323 submissions.