[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

*REMINDER*

THEORY SEMINAR 

Luca Trevisan
U.C. Berkeley
www.cd.berkeley.edu/~luca
 
Title: A Refined Cheeger Inequality and an Improved Analysis of Spectral Partitioning
 
Abstract: The Cheeger inequality in graphs relates the conductance of the graph (a measure of how sparse a cut one can find in the graph) and the second smallest
eigenvalue of the normalized Laplacian matrix of the graph. The inequality also implies a worst-case analysis of the performance of a spectral algorithm of Fiedler to find approximate sparse cuts. The practical performance of Fiedler's algorithm is usually (but not always) much better than the worst-case bound.
 
We prove a refinement of the Cheeger inequality which is never worse than the original one and is better in graphs that have a spectral gap; our analysis also proves an improved performance of Fiedler's algorithm on such graphs.
 
We will also discuss: applications to clustering and to the max cut problem; how to apply similar ideas to the analysis of semidefinite programming relaxations; and a
recent result of Liu who proved an analogous result in the setting of Riemann manifolds.
 
(Joint work with Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, and Shayan Oveis Gharan)

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