Focs 2015 Schedule

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

12:05-12:25

Probabilistic Polynomials and Hamming Nearest Neighbors

Josh Alman, Ryan Williams

Black-Box Garbled RAM

Sanjam Garg, Steve Lu, Rafail Ostrovsky

12:30-1:45

Lunch break

2:00-2:20

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

2:25-2:45

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

2:50-3:10

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

3:15-3:35

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

3:40-4:00

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

4:00-4:30

Coffee break

4:30-4:50

The Average Sensitivity of Bounded-Depth Formulas

Benjamin Rossman

The Submodular Secretary Problem Goes Linear

Moran Feldman, Rico Zenklusen

4:55-5:15

The Power of Asymmetry in Constant-Depth Circuits

Alexander A. Sherstov

Competitive Flow Time Algorithms for Polyhedral Scheduling

Sungjin Im, Janardhan Kulkarni, Kamesh Munagala

5:20-5:40

Deterministic Divisibility Testing via Shifted Partial Derivatives

Michael A. Forbes

Tight Bounds for Online Vector Scheduling

Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, Debmalya Panigrahi

5:45-6:05

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

19
October

8:00-8:45

Breakfast

8:45-9:05

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

9:10-9:30

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

9:35-9:55

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

10:00-10:20

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

10:20-10:50

Coffee break

10:50-11:10

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

11:15-11:35

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

11:40-12:00

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

12:05-12:25

A light metric spanner

Lee-Ad Gottlieb

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

Alan Guo, Elad Haramaty, Madhu Sudan

12:30-1:45

Lunch break

2:00-2:20

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

2:25-2:45

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

2:50-3:10

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

3:15-3:35

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

3:40-4:00

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

4:00-4:30

Coffee break

4:30-4:50

An average-case depth hierarchy theorem for Boolean circuits

[best paper award]

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

4:55-5:15

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

5:20-5:40

Lower Bounds for Clique vs. Independent Set

[best student paper award]

Mika Göös

20
October

8:00-8:45

Breakfast

8:45-9:05

Deterministic Communication vs. Partition Number

Mika Göös, Toniann Pitassi, Thomas Watson

Approximate Modularity

Flavio Chiericetti, Abhimanyu Das, Anirban Dasgupta, Ravi Kumar

9:10-9:30

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

9:35-9:55

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

10:00-10:20

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

10:20-10:50

Coffee break

10:50-11:10

Uniform generation of random regular graphs

Pu Gao, Nicholas Wormald

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

Mikkel Thorup

11:15-11:35

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

11:40-12:00

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

12:05-12:25

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

12:30-1:45

Lunch break

2:00-2:20

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

2:25-2:45

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

2:50-3:10

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

3:15-3:35

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

3:40-4:00

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