58th Annual IEEE Symposium on Foundations of Computer Science

Berkeley, California

15-17 October 2017

Papers By Session

Session 1A
A Nearly Optimal Lower Bound on the Approximate Degree of AC^0
On the Quantitative Hardness of CVP
Distributed PCP Theorems for Hardness of Approximation in P
Short Presburger Arithmetic Is Hard
Session 1B
On the Local Structure of Stable Clustering Instances
Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures
On Learning Mixtures of Well-Separated Gaussians
Session 2A
On Small-Depth Frege Proofs for Tseitin for Grids
Random Θ(log n)-CNFs Are Hard for Cutting Planes
Random Formulas, Monotone Circuits, and Interpolation
Query-to-Communication Lifting for BPP
A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness
Session 2B
A Time Hierarchy Theorem for the LOCAL Model
Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n^{5/4}) Rounds
Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve
Session 3A
Local List Recovery of High-Rate Tensor Codes & Applications
Optimal Repair of Reed-Solomon Codes: Achieving the Cut-Set Bound
Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice
Optimal Interactive Coding for Insertions, Deletions, and Substitutions
The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes
Session 3B
Approximating Geometric Knapsack via L-Packings
Removing Depth-Order Cycles among Triangles: An Efficient Algorithm Generating Triangular Fragments
Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations
Fast & Space-Efficient Approximations of Language Edit Distance and RNA Folding: An Amnesic Dynamic Programming Approach
A Dichotomy for Regular Expression Membership Testing
Session 4
A Dichotomy Theorem for Nonuniform CSPs
A Proof of CSP Dichotomy Conjecture
Session 5A
Learning Graphical Models Using Multiplicative Weights
Active Classification with Comparison Queries
Capacity of Neural Networks for Lifelong Learning of Composable Tasks
Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems
Robust Polynomial Regression up to the Information Theoretic Limit
Session 5B
Quantum SDP-Solvers: Better Upper and Lower Bounds
Quantum Speed-Ups for Solving Semidefinite Programs
Local Hamiltonians Whose Ground States Are Hard to Approximate
On Preparing Ground States of Gapped Hamiltonians: An Efficient Quantum Lovász Local Lemma
Variable-Version Lovász Local Lemma: Beyond Shearer's Bound
Linear Algebraic Analogues of the Graph Isomorphism Problem and the Erdős-Rényi Model
Session 6A
Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams
First Efficient Convergence for Streaming k-PCA: A Global, Gap-Free, and Near-Optimal Rate
Weighted k-Server Bounds via Combinatorial Dichotomies
An Input Sensitive Online Algorithm for the Metric Bipartite Matching Problem
Session 6B
Learning Multi-Item Auctions with (or without) Samples
Oracle-Efficient Online Learning and Auction Design
Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs
Tight Lower Bounds for Differentially Private Selection
Session 7A
How to Achieve Non-Malleability in One or Two Rounds
Two-Round and Non-Interactive Concurrent Non-Malleable Commitments from Time-Lock Puzzles
Garbled Protocols and Two-Round MPC from Bilinear Maps
Obfuscating Compute-and-Compare Programs under LWE
Lockable Obfuscation
White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing
Session 7B
Optimality of the Johnson-Lindenstrauss Lemma
Optimal Compression of Approximate Inner Products and Dimension Reduction
Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average
Fast Similarity Sketching
Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices
Session 8
Hardness Results for Structured Linear Systems
The Matching Problem in General Graphs Is in Quasi-NC
Session 9A
On the Power of Statistical Zero Knowledge
The Power of Sum-of-Squares for Detecting Hidden Structures
A Time-Space Lower Bound for a Large Class of Learning Problems
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
Session 9B
Faster (and Still Pretty Simple) Unbiased Estimators for Network (Un)reliability
Minor-Free Graphs Have Light Spanners
Polylogarithmic Approximation for Minimum Planarization (Almost)
Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time
Session 10A
Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time
Fooling Intersections of Low-Weight Halfspaces
Exponentially-Hard Gap-CSP and Local PRG via Local Hardcore Functions
Session 10B
Testing Hereditary Properties of Ordered Graphs and Matrices
A Characterization of Testable Hypergraph Properties
Boolean Unateness Testing with Õ(n^{3/4}) Adaptive Queries
Generalized Uniformity Testing
Session 11A
Much Faster Algorithms for Matrix Scaling
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices
Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees
Session 11B
Optimal Las Vegas Locality Sensitive Data Structures
Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time
Fast and Compact Exact Distance Oracle for Planar Graphs
Session 12A
High Dimensional Expanders Imply Agreement Expanders
The Ising Partition Function: Zeros and Deterministic Approximation
Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion
Session 12B
Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere
Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration
Hashing-Based-Estimators for Kernel Density in High Dimensions