Many Sparse Cuts via Higher Eigenvalues
Speaker: Santosh Vempala , Georgia Tech
Date: November 15 2011
Time: 4:15PM to 5:15PM
Location: 32-124
Host: Dana Moshkovitz, CSAIL, MIT
Contact: Be Blackburn, 3-6098, be@csail.mit.edu
Relevant URL: Cheeger's fundamental inequality says that any edge-weighted graph has a vertex subset whose weighted expansion (a.k.a. conductance) is bounded by twice the square root of the second smallest eigenvalue of the normalized Laplacian of the graph. This inequality and its algorithmic proof have a myriad of applications.
We present a generalization: for any integer k less than n, there exist c.k disjoint subsets such that the expansion of each one is bounded by C\sqrt{\lambda_k \log k}, where \lambda_k is the k'th largest eigenvalue of the normalized Laplacian and c,C are absolute constants. Our proof is via a polynomial-time algorithm to find such subsets, using spectral projection and randomized rounding and can be seen as an extension of the Cheeger method. As a consequence, we get the same upper bound for the small-set expansion problem, namely for any k, there is a subset whose weight is an O(1/k) fraction of the total weight and its expansion is bounded by C\sqrt{\lambda_k \log k}. Both results are the best possible up to constant factors.
The underlying algorithmic problem, namely finding k subsets such that the maximum expansion is minimized, besides extending sparse cuts to more than one subset, appears to be a natural clustering problem in its own right.
This is joint work with Anand Louis and a couple of Prasads.
See other events that are part of Theory Colloquium 2011/2012
See other events happening in November 2011
