2016 IEEE 57th Annual Symposium on Foundations of Computer Science

New Brunswick, New Jersey

9-11 October 2016

Papers By Session

Session 1.1A
Bounded-Communication Leakage Resilience via Parity-Resilient Circuits
Indistinguishability Obfuscation from DDH-Like Assumptions on Constant-Degree Graded Encodings
Breaking the Three Round Barrier for Non-malleable Commitments
Zero-Knowledge Proof Systems for QMA
Session 1.1B
Strong Fooling Sets for Multi-player Communication with Applications to Deterministic Estimation of Stream Statistics
Edit Distance: Sketching, Streaming, and Document Exchange
Heavy Hitters via Cluster-Preserving Clustering
Optimal Quantile Approximation in Streams
Session 1.2A
An Average-Case Depth Hierarchy Theorem for Higher Depth
A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function
Depth-Reduction for Composites
A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing
Session 1.2B
The Salesman's Improved Paths: A 3/2+1/34 Approximation
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-uniform Distributions
Online Algorithms for Covering and Packing Problems with Convex Objectives
Session 1.3A
Explicit Non-malleable Extractors, Multi-source Extractors, and Almost Optimal Privacy Amplification Protocols
Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy
Extractors for Near Logarithmic Min-Entropy
Making the Most of Advice: New Correlation Breakers and Their Applications
The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling
Session 1.3B
Computational Efficiency Requires Simple Taxation
Learning in Auctions: Regret is Hard, Envy is Easy
On the Communication Complexity of Approximate Fixed Points
Informational Substitutes
Constrained Submodular Maximization: Beyond 1/e
Session 1.4 Best Papers
Settling the Complexity of Computing Approximate Two-Player Nash Equilibria
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning
Ramanujan Graphs in Polynomial Time
Session 2.1A
Structure of Protocols for XOR Functions
The Multiparty Communication Complexity of Interleaved Group Products
How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication
Session 2.1B
Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time
Fully Dynamic Maximal Matching in Constant Update Time
On Fully Dynamic Graph Sparsifiers
Linear Hashing Is Awesome
Session 2.2
Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics
Local Search Yields a PTAS for k-Means in Doubling Metrics
Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product
Session 2.3
Knuth Prize Lecture: Complexity of Communication in Markets
Session 2.4
No Occurrence Obstructions in Geometric Complexity Theory
Rectangular Kronecker Coefficients and Plethysms in Geometric Complexity Theory
Exponential Lower Bounds for Monotone Span Programs
A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents
Session 2.5A
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Polynomial-Time Tensor Decompositions with Sum-of-Squares
Towards Strong Reverse Minkowski-Type Inequalities for Lattices
Session 2.5B
Which Regular Expression Patterns Are Hard to Match?
Polynomial Representations of Threshold Functions and Algorithmic Applications
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms
Session 2.6A
Max-Information, Differential Privacy, and Post-selection Hypothesis Testing
Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism
Session 2.6B
The Constant Inapproximability of the Parameterized Dominating Set Problem
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
Testing Assignments to Constraint Satisfaction Problems
Session 3.1A
Compressing Interactive Communication under Product Distributions
Decidability of Non-interactive Simulation of Joint Distributions
Separations in Communication Complexity Using Cheat Sheets and Information Complexity
Extension Complexity of Independent Set Polytopes
Session 3.1B
Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More
Computing Maximum Flow with Augmenting Electrical Flows
Optimizing Star-Convex Functions
Session 3.2A
An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
Local Conflict Coloring
A Fast and Simple Unbiased Estimator for Network (Un)reliability
A New Framework for Distributed Submodular Maximization
Session 3.2B
Robust Estimators in High Dimensions without the Computational Intractability
Agnostic Estimation of Mean and Covariance
Noisy Population Recovery in Polynomial Time
A New Approach for Testing Properties of Discrete Distributions
Session 3.3A
How to Determine if a Random Graph with a Fixed Degree Sequence Has a Giant Component
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model
Simulated Quantum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing
The Number of Solutions for Random Regular NAE-SAT
Session 3.3B
Accelerated Newton Iteration for Roots of Black Box Polynomials
Fourier-Sparse Interpolation without a Frequency Gap
Robust Fourier and Polynomial Curve Fitting
NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem
Session 3.4A
Amplification and Derandomization without Slowdown
Commutativity in the Algorithmic Lovász Local Lemma
An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound
Session 3.4B
Universal Simulation of Directed Systems in the Abstract Tile Assembly Model Requires Undirectedness
A PTAS for the Steiner Forest Problem in Doubling Metrics
On Approximating Maximum Independent Set of Rectangles