I will present a new proof of Cheeger's inequality, which can be generalized to incorporate robust vertex expansion in it. The proof builds on the ideas of Lovasz and Kannan for analyzing mixing times of random walks. I will also discuss similar analyses for different local graph partitioning algorithms (random walks, pagerank, evolving sets). Finally, I will present an example showing the limitations of local graph partitioning algorithms in attacking the small-set expansion hypothesis, disproving a conjecture by Oveis Gharan about evolving sets.

Joint work with Siu On Chan, Tsz Chiu Kwok, and Yin Tat Lee.

### Tuesday, December 15th, 2015

### Wednesday, December 16th, 2015

In this talk I will discuss faster algorithms and improved sample complexities for the fundamental problem of estimating the top eigenvector of a matrix A^T A. In particular I will show how the classic method of shift-and-invert preconditioning efficiently reduces the top eigenvector problem to the problem of solving a sequence of linear systems. Moreover, by leveraging recent sampling-based linear system solvers I will show how this allows us to obtain improved algorithms for both the offline eigenvector estimation problem where A is given explicitly as well as the online eigenvector estimation problem where we only receive independent samples from A^T A.

^{O(1)}which entails a polynomial time loglog(n)

^{O(1)}-estimation algorithm; that is we provide a polynomial time algorithm that finds the cost of the best possible solution within a loglog(n)

^{O(1)}factor, but does not provide a solution with that cost.

We prove this by making progress on Goddyn's Thin Tree conjecture; we show that every k-edge-connected graph contains a loglog(n)

^{O(1)}/k-thin tree. To tackle the Thin Tree conjecture, we build upon the recent resolution of the Kadison-Singer problem by Marcus, Spielman, and Srivastava. We answer the following question by providing sufficient conditions: Given a set of rank 1 quadratic forms, can we select a subset of them from a given collection of subsets, whose total sum is bounded by a fraction of the sum of all quadratic forms?

^{c}-approximated in polynomial time for any c>0 and that it can be loglog(n)

^{O(1)}-approximated in quasi-polynomial time, assuming access to an oracle which solves our extension of Kadison-Singer.

We study the widely used spectral clustering algorithms, i.e. partition a graph into k clusters via (1) embedding the vertices of a graph into a low-dimensional space using the bottom eigenvectors of the Laplacian matrix, and (2) partitioning the embedded points via k-means algorithms. We show that, for a wide class of graphs, spectral clustering algorithms give a good approximation of the optimal clustering. While this approach was proposed in the early 1990s and has comprehensive applications, prior to our work similar results were known only for graphs generated from stochastic models.

We also give a nearly-linear time algorithm for partitioning well-clustered graphs, which is based on heat kernel embeddings and approximate nearest neighbor data structures.

### Thursday, December 17th, 2015

We consider nonnegative functions on abelian groups that are sparse with respect to the Fourier basis. We establish combinatorial conditions on subsets S and T of Fourier basis elements under which nonnegative functions with Fourier support S are sums of squares of functions with Fourier support T. Our combinatorial condition involves constructing a chordal cover of an associated Cayley Graph. Our result relies on two main ingredients: the decomposition of sparse positive semidefinite matrices with a chordal sparsity pattern, as well as a simple but key observation exploiting the structure of the Fourier basis elements of G.

We apply our general result to two examples. First, in the case where G = Z_2^n, we prove that any nonnegative quadratic form in n binary variables is a sum of squares of functions of degree at most ⌈n/2⌉, establishing a conjecture of Laurent. Second, we consider nonnegative functions of degree d on ℤN (when d divides N). By constructing a particular chordal cover of the d-th power of the N-cycle, we prove that any such function is a sum of squares of functions with at most 3dlog(N/d) nonzero Fourier coefficients. Dually this shows that a certain cyclic polytope in R^(2d) with N vertices has a semidefinite representation of size 3dlog(N/d). Putting N=d^2 gives a family of polytopes with LP extension complexity Ω(d^2) and SDP extension complexity O(dlog(d)). To the best of our knowledge, this is the first explicit family of polytopes whose semidefinite extension complexity is provably smaller than their linear programming extension complexity.

Joint work with Hamza Fawzi and James Saunderson. Preprint available at http://arxiv.org/abs/1503.

Recently, there has been some success in using the sum-of-squares hierarchy to solve classical problems in machine learning. However, the sum-of-squares algorithms are very slow, making them impractical for the machine learning setting. In this talk I will show that ideas from sum-of-squares rounding schemes can be used to obtain fast, spectral algorithms. I will focus on the problem of decomposing an overcomplete low-rank random tensor into rank-1 components, showing that ideas from the quasi-polynomial sum-of-squares algorithm can be adapted to achieve similar performance in subquadratic time.

Based on joint work with Sam Hopkins, Jonathan Shi and David Steurer.

This talk is concerned with clustering random graphs, under "block-model" assumptions, an area that has made remarkable progress recently. In the first part of the talk, I will describe an empirical comparison of the existing recovery theorems for the Degree-Corrected Stochastic Block Model (DC-SBM). The past few years have seen a number of new recovery algorithms with guarantees for this model. Since these represent sufficient conditions, one expects that cases exist which are not covered by the theory, but for which recovery is possible. We explore experimentally the limits of the current theory. We generate benchmark cases, with well defined parameters controlling their difficulty. Then we verify which of the existing results in the literature predict recovery. What we observe suggests that there is more ground to be covered towards deriving sharp thresholds for this problem. The second part of the talk will present a new class of block models recoverable by spectral clustering, that contains the DC-SBM as a special case. This class has O(n^2) free parameters (instead of the DC-SBM's O(n)), yet one can easily obtain the same recovery guarantees known for the DC-SBM, under conditions that expose with more clarity the parameters that control recovery.

Joint work with Yali Wan.

In this talk we will consider finding approximate isoperimetric partitions of a probability distributions given a sample from the distributions. We first consider the case where we are explicitly given the distribution and discuss numerical methods to obtain Cheeger like cuts by reducing the problem to eigenvectors of a graph Laplacian. Second, we look at known unbiased estimators for estimating the PDF from a sample. We will show how the second nearest neighbor estimators can be combine with mesh generation methods to construct a graph Laplacian from a sample. Finally we will show some experimental results on partitioning flow cytometry data related to HIV.

### Friday, December 18th, 2015

We study the satisfiability of ordering constraint satisfaction problems (CSPs) above average. We prove the conjecture of Gutin, van Iersel, Mnich, and Yeo that the satisfiability above average of ordering CSPs of arity k is fixed-parameter tractable for every k. Previously, this was only known for k=2 and k=3. We also generalize this result to more general classes of CSPs, including CSPs with predicates defined by linear inequalities.

To obtain our results, we prove a new Bonami-type inequality for the Efron-Stein decomposition. The inequality applies to functions defined on arbitrary product probability spaces. In contrast to other variants of the Bonami Inequality, it does not depend on the mass of the smallest atom in the probability space. We believe that this inequality is of independent interest.

This talk is based on a joint work with Konstantin Makarychev and Yuan Zhou.

In the talk, I will describe the Correlation Clustering problem and give an overview of known results. I will present a new 2.06 approximation algorithm for the problem on complete graphs. Then, I will describe a semi-random model for the Correlation Clustering problem with noisy partial information, and give PTAS for semi-random instances.

Based on joint works with Shuchi Chawla, Tselil Schramm, and Grigory Yaroslavtsev; and with Yury Makarychev and Aravindan Vijayaraghavan.

Inspired by computational abilities of the organism slime mold, several researchers have recently proposed dynamical systems aimed at solving fundamental problems such as min-cost flow and, more generally, linear programming. In this talk I will present these dynamics from an optimization viewpoint and show that they provably work. Together, these results shed some light on how nature might be solving instances of perhaps the most complex problem in P: linear programming.

This is based on joint works with Damian Straszak (EPFL).