FOCS 2015

Sponsored by

IEEE logo IEEE Computer Society logo Microsoft Research logo Simons Institute for the Theory of Computing logo

2015 IEEE 56th Annual Symposium on Foundations of Computer Science

Berkeley, California

Exhibition Dates: 18-20 October 2015

Conference Information

Preface
Organizing Committee and Sponsors
Program Committee
External Reviewers
Awards
Author Index
Publisher's Information

Papers By Session

Session 1
Approximating ATSP by Relaxing Connectivity
by Ola Svensson
Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP
by Nima Anari, Shayan Oveis Gharan
Compressing and Teaching for Low VC-Dimension
by Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
On Monotonicity Testing and Boolean Isoperimetric Type Theorems
by Subhash Khot, Dor Minzer, Muli Safra
Session 2A
Tight Hardness Results for LCS and Other Sequence Similarity Measures
by Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
by Karl Bringmann, Marvin Künnemann
If the Current Clique Algorithms are Optimal, So is Valiant's Parser
by Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems
by Barna Saha
Probabilistic Polynomials and Hamming Nearest Neighbors
by Josh Alman, Ryan Williams
Session 2B
Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption
by Craig Gentry, Allison Bishop Lewko, Amit Sahai, Brent Waters
Indistinguishability Obfuscation from Functional Encryption
by Nir Bitansky, Vinod Vaikuntanathan
Limits on the Power of Indistinguishability Obfuscation and Functional Encryption
by Gilad Asharov, Gil Segev
Black-Box Garbled RAM
by Sanjam Garg, Steve Lu, Rafail Ostrovsky
Session 3A
Efficient Inverse Maintenance and Faster Algorithms for Linear Programming
by Yin Tat Lee, Aaron Sidford
Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
by Yin Tat Lee, He Sun
Guaranteed Matrix Completion via Nonconvex Factorization
by Ruoyu Sun, Zhi-Quan Luo
Heavy-Tailed Independent Component Analysis
by Joseph Anderson, Navin Goyal, Anupama Nandi, Luis Rademacher
Input Sparsity and Hardness for Robust Subspace Approximation
by Kenneth L. Clarkson, David P. Woodruff
Session 3B
The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication
by Erez Kantor, Zvi Lotker, Merav Parter, David Peleg
Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks
by John Augustine, Gopal Pandurangan, Peter Robinson, Scott Roche, Eli Upfal
Planar Reachability in Linear Space and Constant Time
by Jacob Holm, Eva Rotenberg, Mikkel Thorup
Towards an Optimal Method for Dynamic Planar Point Location
by Timothy M. Chan, Yakov Nekrich
Pattern-Avoiding Access in Binary Search Trees
by Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak
Session 4A
The Average Sensitivity of Bounded-Depth Formulas
by Benjamin Rossman
The Power of Asymmetry in Constant-Depth Circuits
by Alexander A. Sherstov
Deterministic Divisibility Testing via Shifted Partial Derivatives
by Michael A. Forbes
Hardness of Approximation in PSPACE and Separation Results for Pebble Games
by Siu Man Chan, Massimo Lauria, Jakob Nordstrom, Marc Vinyals
Session 4B
The Submodular Secretary Problem Goes Linear
by Moran Feldman, Rico Zenklusen
Competitive Flow Time Algorithms for Polyhedral Scheduling
by Sungjin Im, Janardhan Kulkarni, Kamesh Munagala
Tight Bounds for Online Vector Scheduling
by Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, Debmalya Panigrahi
Online Buy-at-Bulk Network Design
by Alina Ene, Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Debmalya Panigrahi
Session 5A
Solving the Closest Vector Problem in 2n Time—The Discrete Gaussian Strikes Again!
by Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz
A Robust Sparse Fourier Transform in the Continuous Setting
by Eric Price, Zhao Song
Breaking the Variance: Approximating the Hamming Distance in 1/ε Time Per Alignment
by Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette
Approximately Counting Triangles in Sublinear Time
by Talya Eden, Amit Levi, Dana Ron, C. Seshadhri
Session 5B
Differentially Private Release and Learning of Threshold Functions
by Mark Bun, Kobbi Nissim, Uri Stemmer, Salil Vadhan
Robust Traceability from Trace Amounts
by Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, Salil Vadhan
Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery
by Emmanuel Abbe, Colin Sandon
How to Refute a Random CSP
by Sarah R. Allen, Ryan O'Donnell, David Witmer
Session 6A
An O(1)-Approximation for Minimum Spanning Tree Interdiction
by Rico Zenklusen
Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line
by Amir Nayyeri, Benjamin Raichel
Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem
by F.B. Shepherd, Adrian Vetta, Gordon T. Wilfong
A Light Metric Spanner
by Lee-Ad Gottlieb
Session 6B
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters
by Dominic W. Berry, Andrew M. Childs, Robin Kothari
Quantum Expander Codes
by Anthony Leverrier, Jean-Pierre Tillich, Gilles Zémor
Robust Testing of Lifted Codes with Applications to Low-Degree Testing
by Alan Guo, Elad Haramaty, Madhu Sudan
Session 7A
Local Correlation Breakers and Applications to Three-Source Extractors and Mergers
by Gil Cohen
Three-Source Extractors for Polylogarithmic Min-Entropy
by Xin Li
Beyond the Central Limit theorem: Asymptotic Expansions and Pseudorandomness for Combinatorial Sums
by Anindya De
Pseudorandomness via the Discrete Fourier Transform
by Parikshit Gopalan, Daniek Kane, Raghu Meka
Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions
by Vitaly Feldman, Jan Vondrák
Session 7B
Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable
by Helmut Seidl, Sebastian Maneth, Gregor Kemper
FO Model Checking on Posets of Bounded Width
by Jakub Gajarský, Petr Hlinený, Daniel Lokshtanov, Jan Obdržálek, Sebastian Ordyniak, M.S. Ramanujan, Saket Saurabh
Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable
by Konstantin Makarychev, Yury Makarychev, Yuan Zhou
Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k
by Radu Curticapean, Mingji Xia
Isomorphism Testing for Graphs of Bounded Rank Width
by Martin Grohe, Pascal Schweitzer
Session 8
An Average-Case Depth Hierarchy Theorem for Boolean Circuits
by Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
by Yin Tat Lee, Aaron Sidford, Sam Chiu-Wai Wong
Lower Bounds for Clique vs. Independent Set
by Mika Göös
Session 9A
Deterministic Communication vs. Partition Number
by Mika Göös, Toniann Pitassi, Thomas Watson
New Unconditional Hardness Results for Dynamic and Online Problems
by Raphaël Clifford. Allan Grønlund, Kasper Green Larsen
Tight Hardness of the Non-commutative Grothendieck Problem
by Jop Briøt, Oded Regev, Rishi Saket
No Small Linear Program Approximates Vertex Cover within a Factor 2\ndash; ε
by Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta, Ola Svensson
Session 9B
Approximate Modularity
by Flavio Chiericetti, Abhimanyu Das, Anirban Dasgupta, Ravi Kumar
Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability
by Eldar Fischer, Oded Lachish, Yadu Vasudev
Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions
by Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin
On the Structure, Covering, and Learning of Poisson Multinomial Distributions
by Constantinos Daskalakis, Gautam Kamath, Christos Tzamos
Session 10A
Uniform Generation of Random Regular Graphs
by Pu Gao, Nicholas Wormald
Symbolic Integration and the Complexity of Computing Averages
by Leonard J. Schulman, Alistair Sinclair, Piyush Srivastava
The Complexity of General-Valued CSPs
by Vladimir Kolmogorov, Andrei Krokhin, Michal Rolínek
A Holant Dichotomy: Is the FKT Algorithm Universal?
by Jin-Yi Cai, Zhiguo Fu, Heng Guo, Tyson Williams
Session 10B
Sample (x) = (a*x<=t) is a Distinguisher with Probability 1/8
by Mikkel Thorup
Hashing for Statistics over K-Partitions
by Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, Mikkel Thorup
Optimal Induced Universal Graphs and Adjacency Labeling for Trees
by Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen
An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles
by Nicholas J.A. Harvey, Jan Vondrák
Session 11A
Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs
by Charles Bordenave, Marc Lelarge, Laurent Massoulié
Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes
by Adam W. Marcus, Daniel A. Spielman, Nikhil Srivastava
Incidences between Points and Lines in R4
by Micha Sharir, Noam Solomon
Talagrand's Convolution Conjecture on Gaussian Space
by Ronen Eldan, James R. Lee
Random Matrices: l1 Concentration and Dictionary Learning with Few Samples
by Kyle Luh, Van Vu
Session 11B
Mixture Selection, Mechanism Design, and Signaling
by Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, Shang-Hua Teng
Optimal Auctions vs. Anonymous Pricing
by Saeed Alaei, Jason Hartline, Rad Niazadeh, Emmanouil Pountourakis, Yang Yuan
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms
by Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
On the Cryptographic Hardness of Finding a Nash Equilibrium
by Nir Bitansky, Omer Paneth, Alon Rosen
Welfare Maximization with Limited Interaction
by Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein