[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

*REMINDER*

THEORY SEMINAR

Tuesday, February 12, 2013
3:00 p.m.
Ryerson 251
 
James Lee
University of Washington
homes.cs.washington.edu/~jrl/
 
 
Title:  Multi-way spectral partitioning and higher-order Cheeger inequalities
 
Abstract: A basic fact in spectral 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.  The discrete Cheeger inequality and its variants provide a "stable" quantitative version of this fact; they state that a graph has a non-expanding 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 non-expanding cut.  We resolve this conjecture. Our result provides a theoretical justification for clustering algorithms that use the bottom k eigenvectors to embed the vertices into R^k, and then apply geometric methods to the embedding.   We extend these techniques to exhibit a nearly optimal quantitative connection between the expansion of sets of size n/k and the k-th smallest eigenvalue of the Laplacian.
 
Joint work with Shayan Oveis Gharan and Luca Trevisan.
 
Host: Jian Ding (Stat) & Madhur Tulsiani (TTIC)
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20130212/de03175f/attachment.htm