Focs 2015 Schedule

18th–20th of October 2015 | DoubleTree Hotel at the Berkeley Marina, Berkeley, California


Probabilistic Polynomials and Hamming Nearest Neighbors

Josh Alman, Ryan Williams

Black-Box Garbled RAM

Sanjam Garg, Steve Lu, Rafail Ostrovsky


Lunch break


Efficient Inverse Maintenance and Faster Algorithms for Linear Programming

Yin Tat Lee, Aaron Sidford

The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication

Erez Kantor, Zvi Lotker, Merav Parter, David Peleg


Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

Yin Tat Lee, He Sun

Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks

John Augustine, Gopal Pandurangan, Peter Robinson, Scott Roche, Eli Upfal


Guaranteed Matrix Completion via Non-convex Factorization

Ruoyu Sun, Zhi-Quan Luo

Planar Reachability in Linear Space and Constant Time

Jacob Holm, Eva Rotenberg, Mikkel Thorup


Heavy-tailed Independent Component Analysis

Joseph Anderson, Navin Goyal, Anupama Nandi, Luis Rademacher,

Towards an Optimal Method for Dynamic Planar Point Location

Timothy M. Chan, Yakov Nekrich


Input Sparsity and Hardness for Robust Subspace Approximation

Kenneth L. Clarkson, David P. Woodruff

Pattern-avoiding access in binary search trees

Parinya Chalermsook, Mayank Goswami, Laszlo Kozma, Kurt Mehlhorn, Thatchaphol Saranurak


Coffee break


The Average Sensitivity of Bounded-Depth Formulas

Benjamin Rossman

The Submodular Secretary Problem Goes Linear

Moran Feldman, Rico Zenklusen


The Power of Asymmetry in Constant-Depth Circuits

Alexander A. Sherstov

Competitive Flow Time Algorithms for Polyhedral Scheduling

Sungjin Im, Janardhan Kulkarni, Kamesh Munagala


Deterministic Divisibility Testing via Shifted Partial Derivatives

Michael A. Forbes

Tight Bounds for Online Vector Scheduling

Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, Debmalya Panigrahi


Hardness of Approximation in PSPACE and Separation Results for Pebble Games

Siu Man Chan, Massimo Lauria, Jakob Nordstrom, Marc Vinyals

Online Buy-at-Bulk Network Design

Alina Ene, Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Debmalya Panigrahi

9 p.m.

Business meeting





Solving the Closest Vector Problem in 2^n Time : The Discrete Gaussian Strikes Again!

Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz

Differentially Private Release and Learning of Threshold Functions

Mark Bun, Kobbi Nissim, Uri Stemmer, Salil Vadhan


A Robust Sparse Fourier Transform in the Continuous Setting

Eric Price, Zhao Song

Robust Traceability from Trace Amounts

Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, Salil Vadhan


Breaking the Variance: Approximating the Hamming Distance in O~{1/\epsilon} Time Per Alignment

Tsvi Kopelowitz ,Ely Porat

Community detection in the general stochastic block model: fundamental limits and efficient algorithms for recovery

Emmanuel Abbe, Colin Sandon


Approximately Counting Triangles in Sublinear Time

Talya Eden, Amit Levi, Dana Ron, C. Seshadhri

How to refute a random CSP

Sarah R. Allen, Ryan O'Donnell, David Witmer


Coffee break


An O{1}-Approximation for Minimum Spanning Tree Interdiction

Rico Zenklusen

Near-optimal bounds on bounded-round quantum communication complexity of disjointness

Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette


Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line

Amir Nayyeri, Benjamin Raichel

Hamiltonian simulation with nearly optimal dependence on all parameters

Dominic William Berry, Andrew MacGregor Childs, Robin Kothari


Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem

F.B. Shepherd, Adrian Vetta, Gordon T. Wilfong

Quantum Expander Codes

Anthony Leverrier, Jean-Pierre Tillich, Gilles Zémor


A light metric spanner

Lee-Ad Gottlieb

Robust testing of lifted codes with applications to low-degree testing

Alan Guo, Elad Haramaty, Madhu Sudan


Lunch break


Local Correlation Breakers and Applications to Three-Source Extractors and Mergers

Gil Cohen

Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable

Helmut Seidl, Sebastian Maneth, Gregor Kemper


Three-Source Extractors for Polylogarithmic Min-Entropy

Xin Li

FO Model Checking on Posets of Bounded Width

Jakub Gajarsky, Petr Hlineny, Daniel Lokshtanov, Jan Obdrzalek, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh


Beyond the central limit theorem: Asymptotic expansions and pseudorandomness for combinatorial sums

Anindya De

Satisfiability of Ordering CSPs Above Average Is Fixed-Parameter Tractable

Konstantin Makarychev, Yury Makarychev, Yuan Zhou


Pseudorandomness via the discrete Fourier transform

Parikshit Gopalan, Daniel Kane, Raghu Meka

Parameterizing the Permanent: genus, apices, minors, evaluation mod 2^k

Radu Curticapean, Mingji Xia


Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS functions

Vitaly Feldman, Jan Vondrak

Isomorphism Testing for Graphs of Bounded Rank Width

Martin Grohe, Pascal Schweitzer


Coffee break


An average-case depth hierarchy theorem for Boolean circuits

[best paper award]

Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan


A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization

[best student paper award]

Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong


Lower Bounds for Clique vs. Independent Set

[best student paper award]

Mika Göös





Deterministic Communication vs. Partition Number

Mika Göös, Toniann Pitassi, Thomas Watson

Approximate Modularity

Flavio Chiericetti, Abhimanyu Das, Anirban Dasgupta, Ravi Kumar


New Unconditional Hardness Results for Dynamic and Online Problems

Raphael Clifford. Allan Gronlund, Kasper Green Larsen

Trading query complexity for sample-based testing and multi-testing scalability

Eldar Fischer, Oded Lachish, Yadu Vasudev


Tight Hardness of the Non-commutative Grothendieck Problem

Jop Briet, Oded Regev, Rishi Saket

Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions

Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin


No Small Linear Program Approximates Vertex Cover within a Factor 2 - \epsilon

Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta, Ola Svensson

On the Structure, Covering, and Learning of Poisson Multinomial Distributions

Constantinos Daskalakis, Gautam Kamath, Christos Tzamos


Coffee break


Uniform generation of random regular graphs

Pu Gao, Nicholas Wormald

Sample{x}={a*x< =t} is a distinguisher with probability 1/8

Mikkel Thorup


Symbolic integration and the complexity of computing averages

Leonard J. Schulman, Alistair Sinclair, Piyush Srivastava

Hashing for statistics over k-partitions

Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, Mikkel Thorup


The Complexity of General-Valued CSPs

Vladimir Kolmogorov, Andrei Krokhin, Michal Rolinek

Optimal induced universal graphs and adjacency labeling for trees

Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen


A Holant Dichotomy: Is the FKT Algorithm Universal?

Jin-Yi Cai, Zhiguo Fu, Heng Guo, Tyson Williams

An algorithmic proof of the Lovasz Local Lemma via resampling oracles

Nicholas J. A. Harvey, Jan Vondrak


Lunch break


Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs

Charles Bordenave, Marc Lelarge, Laurent Massoulie

Mixture Selection, Mechanism Design, and Signaling

Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, Shang-Hua Teng


Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes

Adam W. Marcus, Daniel A. Spielman, Nikhil Srivastava

Optimal Auction vs. Anonymous Pricing

Saeed Alaei, Jason Hartline, Rad Niazadeh, Emmanouil Pountourakis, Yang Yuan


Incidences between points and lines in R^4

Micha Sharir, Noam Solomon

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms

Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis


Talagrand's convolution conjecture on Gaussian space

Ronen Eldan, James R. Lee

On the Cryptographic Hardness of Finding a Nash Equilibrium

Nir Bitansky, Omer Paneth, Alon Rosen


Random Matrices: l1 Concentration and Dictionary Learning with Few Samples

Kyle Luh, Van Vu

Welfare Maximization with Limited Interaction

Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein