FOCS 2017

Sponsored by

ieee logo ieee cs logo simons logo ibm research logo microsoft logo nsf logo

58th Annual IEEE Symposium on Foundations of Computer Science

Berkeley, California

15-17 October 2017

Conference Information

Copyright Page
Preface
Organizing Committee and Sponsors
Program Committee
External Reviewers
Awards
Author Index

Papers By Session

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

This site and all contents (unless otherwise noted) are Copyright ©2017 IEEE. All rights reserved.