FOCS 2015 Accepted Papers

• Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS functions
  Vitaly Feldman and Jan Vondrak (IBM Almaden Research Center)


• Approximate Modularity
  Flavio Chierichetti (Sapienza University), Abhimanyu Das (Google), Anirban Dasgupta (IIT Gandhinagar), Ravi Kumar (Google)


• Approximating ATSP by Relaxing Connectivity
  Ola Svensson (EPFL)


• Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP
  Nima Anari (UC Berkeley), Shayan Oveis Gharan (University of Washington)


• An O(1)-Approximation for Minimum Spanning Tree Interdiction
  Rico Zenklusen (ETH Zurich)


• Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line
  Amir Nayyeri (Oregon State University), Benjamin Raichel (University of Illinois, Urbana-Champaign)


• Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem
  Bruce Shepherd, Adrian Vetta (McGill), Gordon Wilfong (Bell Labs)


• Tight Hardness of the Non-commutative Grothendieck Problem
  Jop Briet (CWI), Oded Regev (NYU), Rishi Saket (IBM Research)


• No Small Linear Program Approximates Vertex Cover within a Factor 2 - \epsilon
  Abbas Bazzi (EPFL), Samuel Fiorini (Universite libre de Bruxelles), Sebastian Pokutta (Georgia Tech), Ola Svensson (EPFL)


• Hardness of Approximation in PSPACE and Separation Results for Pebble Games
  Siu Man Chan (University of Toronto), Massimo Lauria, Jakob Nordstrom, Marc Vinyals (KTH Royal Institute of Technology)


• Lower Bounds for Clique vs. Independent Set
  Mika Göös (University of Toronto)


• Deterministic Communication vs. Partition Number
  Mika Göös, Toniann Pitassi, and Thomas Watson (University of Toronto)


• Welfare Maximization with Limited Interaction
  Noga Alon (Tel Aviv University and MSR Israel), Noam Nisan (Hebrew University and MSR Israel), Ran Raz (Weizmann Institue and IAS, Princeton), Omri Weinstein (Princeton University)


• Near-optimal bounds on bounded-round quantum communication complexity of disjointness
  Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao (Princeton University), Dave Touchette (Université de Montréal)


• Hamiltonian simulation with nearly optimal dependence on all parameters
  Dominic W. Berry (Macquarie University), Andrew M. Childs (University of Waterloo and University of Maryland), Robin Kothari (University of Waterloo and Massachusetts Institute of Technology)


• Quantum Expander Codes
  Anthony Leverrier, Jean-Pierre Tillich (INRIA), Gilles Zémor (Bordeaux University)


• An average-case depth hierarchy theorem for Boolean circuits
  Benjamin Rossman (NII, Tokyo and Simons Institute), Rocco A. Servedio (Columbia University), Li-Yang Tan (Simons Institute)


• The Average Sensitivity of Bounded-Depth Formulas
  Benjamin Rossman (NII, Tokyo and Simons Institute)


• The Power of Asymmetry in Constant-Depth Circuits
  Alexander Sherstov (UCLA)


• Deterministic Divisibility Testing via Shifted Partial Derivatives
  Michael A. Forbes (Institute for Advanced Study)


• The Complexity of General-Valued CSPs
  Vladimir Kolmogorov (IST Austria), Andrei Krokhin (Durham University, UK), Michal Rolinek (IST Austria)


• Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable
  Helmut Seidl (TU München), Sebastian Maneth (University of Edinburgh), Gregor Kemper (TU München)


• Tight Hardness Results for LCS and other Sequence Similarity Measures
  Amir Abboud (Stanford University), Arturs Backurs (MIT), Virginia Vassilevska Williams (Stanford University)


• Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
  Karl Bringmann (ETH Zurich), Marvin Künnemann (Max Planck Institute, Saarbrücken)


• If the Current Clique Algorithms are Optimal, so is Valiant's Parser
  Amir Abboud (Stanford University), Arturs Backurs (MIT), Virginia Vassilevska Williams (Stanford University)


• Uniform generation of random regular graphs
  Pu Gao (University of Waterloo), Nicholas Wormald (Monash University)


• A Holant Dichotomy: Is the FKT Algorithm Universal?
  Jin-Yi Cai (University of Wisconsin-Madison), Zhiguo Fu (Jilin University), Heng Guo, Tyson Williams (University of Wisconsin-Madison)


• Symbolic integration and the complexity of computing averages
  Leonard Schulman (Caltech), Alistair Sinclair (UC Berkeley), Piyush Srivastava (Caltech)


• Community detection in the general stochastic block model: fundamental limits and efficient algorithms for recovery
  Emmanuel Abbe and Colin Sandon (Princeton University)


• Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs
  Charles Bordenave (CNRS), Marc Lelarge (INRIA-ENS), Laurent Massoulie (INRIA-MSR)


• How to refute a random CSP
  Sarah R. Allen, Ryan O'Donnell, and David Witmer (Carnegie Mellon University)


• Black-Box Garbled RAM
  Sanjam Garg (UC Berkeley), Steve Lu (UCLA), and Rafail Ostrovsky (UCLA)


• Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption
  Craig Gentry (IBM), Allison Bishop Lewko (Columbia University), Amit Sahai (UCLA), Brent Waters (University of Texas at Austin)


• Indistinguishability Obfuscation from Functional Encryption
  Nir Bitansky and Vinod Vaikuntanathan (MIT)


• Limits on the Power of Indistinguishability Obfuscation and Functional Encryption
  Gilad Asharov and Gil Segev (Hebrew University)


• Optimal induced universal graphs and adjacency labeling for trees
  Stephen Alstrup, Sĝren Dahlgaard, and Mathias Bĉk Tejs Knudsen (University of Copenhagen)


• New Unconditional Hardness Results for Dynamic and Online Problems
  Raphael Clifford (Bristol University), Allan Grĝnlund (Aarhus University), Kasper Green Larsen (Aarhus University)


• Towards an Optimal Method for Dynamic Planar Point Location
  Timothy M. Chan and Yakov Nekrich (University of Waterloo)


• Pattern-avoiding access in binary search trees
  Parinya Chalermsook, Mayank Goswami (Max Planck Institute, Saarbrücken), Laszlo Kozma (Saarland University), Kurt Mehlhorn (Max-Planck Institute, Saarbrücken), Thatchaphol Saranurak (KTH Royal Institute of Technology)


• Planar Reachability in Linear Space and Constant Time
  Jacob Holm, Eva Rotenberg, and Mikkel Thorup (University of Copenhagen)


• The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication
  Erez Kantor (MIT), Zvi Lotker (Ben Gurion University), Merav Parter (Weizmann Institute), David Peleg (Weizmann Institute)


• Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks
  John Augustine (IIT Madras), Gopal Pandurangan (University of Houston), Peter Robinson (Queen's University Belfast), Scott Roche (Northeastern University), Eli Upfal (Brown University)


• Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems
  Barna Saha (University of Massachusetts Amherst)


• Probabilistic Polynomials and Hamming Nearest Neighbors
  Josh Alman and Ryan Williams (Stanford University)


• Breaking the Variance: Approximating the Hamming Distance in O~(1/\epsilon) Time Per Alignment
  Tsvi Kopelowitz (University of Michigan), Ely Porat (Bar Ilan University)


• Efficient Inverse Maintenance and Faster Algorithms for Linear Programming
  Yin Tat Lee and Aaron Sidford (MIT)


• A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
  Yin Tat Lee (MIT), Aaron Sidford (MIT), Sam Chiu-wai Wong (UC Berkeley)


• Solving the Closest Vector Problem in 2^n Time : The Discrete Gaussian Strikes Again!
  Divesh Aggarwal (EPFL), Daniel Dadush (CWI), Noah Stephens-Davidowitz (NYU)


• Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
  Yin Tat Lee (MIT), He Sun (University of Bristol)


• FO Model Checking on Posets of Bounded Width
  Jakub Gajarsky (Masaryk University), Petr Hlineny (Masaryk University), Daniel Lokshtanov (University of Bergen), Jan Obdrzalek (Masaryk University), Sebastian Ordyniak (Masaryk University), M. S. Ramanujan (University of Bergen), Saket Saurabh (University of Bergen and IMSc Chennai)


• Satisfiability of Ordering CSPs Above Average Is Fixed-Parameter Tractable
  Konstantin Makarychev (Microsoft Research), Yury Makarychev (TTI Chicago), Yuan Zhou (MIT)


• Parameterizing the Permanent: genus, apices, minors, evaluation mod 2^k
  Radu Curticapean (Saarland University), Mingji Xia (Chinese Academy of Sciences)


• On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms
  Xi Chen (Columbia University), Ilias Diakonikolas (University of Edinburgh), Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis (Columbia University)


• On the Cryptographic Hardness of Finding a Nash Equilibrium
  Nir Bitansky (MIT), Omer Paneth (Boston University), Alon Rosen (IDC Herzliya)


• Optimal Auction vs. Anonymous Pricing
  Saeed Alaei (Google Research), Jason Hartline (Northwestern University), Rad Niazadeh (Cornell University), Emmanouil Pountourakis (Northwestern University), Yang Yuan (Cornell University)


• Noise-stable mixture selection, mechanism design and signaling
  Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, Shang-Hua Teng (USC)


• Isomorphism Testing for Graphs of Bounded Rank Width
  Martin Grohe and Pascal Schweitzer (RWTH Aachen University)


• A light metric spanner
  Lee-Ad Gottlieb (Ariel University)


• Sample(x)=(a*x< =t) is a distinguisher with probability 1/8
  Mikkel Thorup (University of Copenhagen)


• Hashing for statistics over k-partitions
  Sĝren Dahlgaard, Mathias Bĉk Tejs Knudsen, Eva Rotenberg, and Mikkel Thorup (University of Copenhagen)


• An algorithmic proof of the Lovasz Local Lemma via resampling oracles
  Nicholas Harvey (University of British Columbia), Jan Vondrak (IBM Almaden Research Center)


• Incidences between points and lines in R^4
  Micha Sharir and Noam Solomon (Tel Aviv University)


• Talagrand's convolution conjecture on Gaussian space
  Ronen Eldan and James R. Lee (University of Washington)


• Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes
  Adam W. Marcus (Crisply, Yale University), Daniel A. Spielman (Yale University), Nikhil Srivastava (UC Berkeley)


• Compressing and teaching for low VC-dimension
  Shay Moran (Technion), Amir Shpilka (Tel Aviv University), Avi Wigderson (IAS, Princeton), Amir Yehudayoff (Technion)


• On the Structure, Covering, and Learning of Poisson Multinomial Distributions
  Constantinos Daskalakis, Gautam Kamath, Christos Tzamos (MIT)


• Random Matrices: l1 Concentration and Dictionary Learning with Few Samples
  Kyle Luh and Van Vu (Yale University)


• Guaranteed Matrix Completion via Non-convex Factorization
  Ruoyu Sun and Zhi-Quan Luo (University of Minnesota)


• Heavy-tailed Independent Component Analysis
  Joseph Anderson (Ohio State University), Navin Goyal (Microsoft Research), Anupama Nandi, Luis Rademacher (Ohio State University)


• Input Sparsity and Hardness for Robust Subspace Approximation
  Kenneth L. Clarkson and David P. Woodruff (IBM Almaden Research Center)


• The Submodular Secretary Problem Goes Linear
  Moran Feldman (EPFL), Rico Zenklusen (ETH Zurich)


• Competitive Flow Time Algorithms for Polyhedral Scheduling
  Sungjin Im (University of California, Merced), Janardhan Kulkarni, Kamesh Munagala (Duke University)


• Online Buy-at-Bulk Network Design
  Deeparnab Chakrabarty (Microsoft Research), Alina Ene (University of Warwick), Ravishankar Krishnaswamy (Microsoft Research), Debmalya Panigrahi (Duke Univiersity)


• Tight Bounds for Online Vector Scheduling
  Sungjin Im (University of California, Merced), Nathaniel Kell, Janardhan Kulkarni, Debmalya Panigrahi (Duke University)


• Differentially Private Release and Learning of Threshold Functions
  Mark Bun (Harvard University), Kobbi Nissim (Ben-Gurion University and Harvard University), Uri Stemmer (Ben-Gurion University), Salil Vadhan (Harvard University)


• Robust Traceability from Trace Amounts
  Cynthia Dwork (Microsoft Research), Adam Smith (Pennsylvania State University), Thomas Steinke (Harvard University), Jonathan Ullman (Columbia University), Salil Vadhan (Harvard University)


• Local Correlation Breakers and Applications to Three-Source Extractors and Mergers
  Gil Cohen (Weizmann Institute of Science)


• Three-Source Extractors for Polylogarithmic Min-Entropy
  Xin Li (Johns Hopkins University)


• Beyond the central limit theorem: Asymptotic expansions and pseudorandomness for combinatorial sums
  Anindya De (IAS / DIMACS)


• Pseudorandomness via the discrete Fourier transform
  Parikshit Gopalan (Microsoft Research), Daniel M. Kane (UC San Diego), Raghu Meka (UCLA)


• On Monotonicity Testing and Boolean Isoperimetric type Theorems
  Subhash Khot (New York University), Dor Minzer, Muli Safra (Tel Aviv University)


• Trading query complexity for sample-based testing and multi-testing scalability
  Eldar Fischer (Technion), Oded Lachish (Birkbeck, University of London), Yadu Vasudev (Technion)


• Robust testing of lifted codes with applications to low-degree testing
  Alan Guo (MIT), Elad Haramaty (Northeastern University), Madhu Sudan (Microsoft Research)


• Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions
  Ilias Diakonikolas (University of Edinburgh), Daniel Kane (UC San Diego), Vladimir Nikishkin (University of Edinburgh)


• Approximately Counting Triangles in Sublinear Time
  Talya Eden, Amit Levi, Dana Ron (Tel Aviv University), C. Seshadhri (UC Santa Cruz)


• A Robust Sparse Fourier Transform in the Continuous Setting
  Eric Price and Zhao Song (University of Texas at Austin)