The Hebrew University of Jerusalem Einstein Institute of Mathematics		The Hebrew University of Jerusalem The Rachel and Selim Benin School of Computer Science & Engineering
Center for Theoretical Computer Science and Discrete Mathematics

Lectures:

1. A higher-order Cheeger Inequality
   Thursday, May 3rd    4:00 pm    Mathematics Building, Lecture Hall 2    Department Colloquium
   Abstract
   A basic fact in algebraic graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph is disconnected if and only if there are at least two eigenvalues equal to zero.

   Cheeger's inequality and its variants provide an approximate version of the latter fact; they state that a graph has a sparse cut if and only if there are at least two eigenvalues that are close to zero.

   It has been conjectured that an analogous characterization holds for higher multiplicities, i.e., there are k eigenvalues close to zero if and only if the vertex set can be partitioned into k subsets, each defining a sparse cut.

   In this lecture we describe joint work with James Lee and Shayan Oveis Gharan in which we resolve this conjecture.

2. Dimension-reduction and multi-way spectral partitioning
   Monday, May 7th,    11:00 am    Ross Building, Room 201
   Abstract
   In the previous lecture we outlined a proof that if the normalized Laplacian matrix of a graph has k eigenvalues smaller than epsilon, then there are k disjoint subsets of vertices each of expansion at most O(k^2 * epsilon^1/2 ). Via dimension-reduction techniques, we show that it is also possible to find 0.99*k disjoint subsets of vertices, each of expansion at most O( (epsilon * log k)^1/2 ), which is a tight result.

   This lecture describes joint work with James Lee and Shayan Oveis Gharan.

3. Approximating the expansion profile
   Wednesday, May 9th    10:30 am    Ross Building, Room 201
   Abstract
   In the "expansion profile" problem and the "small-set expander" problem we are interested in the following question: given a graph and a parameter k, find the subset of k or fewer vertices with the smallest expansion.

   Using the "evolving sets" algorithm of Anderson and Peres, we provide the following approximation guarantee: if there is a set of size at most k and expansion epsilon, we can find a set of size at most k*n^(1/c) and expansion at most O( (c * epsilon)^(1/2) ). Furthermore, the running time of the algorithm is nearly-linear in the size of the output set. This is the first algorithm for the expansion profile problem that does not lose factors of (log n)^(Omega(1)) in the expansion.

   This lecture describes joint work with Shayan Oveis Gharan.