BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/339
DTSTAMP:20230914T125920Z
SUMMARY:Cutting Graphs Using Eigenvectors\, a.k.a. Cheeger's Inequality
DESCRIPTION:Speaker: Rakesh Venkat\n\nAbstract: \nHow does one partition th
e vertex set of a graph into two parts $(S\,S^C)$\, so that the ratio of e
dges going across to the Volume (number of edges incident on vertices in S
) in the vertex set is as small as possible? This quantity is often referr
ed to as the Sparsity $\\phi(S)$ of the cut\, and finding the sparsest c
ut $\\phi(G)$ in a graph $G$ is an important problem\, used as a subroutin
e in many algorithmic tasks\, like spectral clustering. A widely-used meth
od is based on the spectrum of the Laplacian of the graph\, and is referre
d to as spectral partitioning.\nThe method is based on the following inequ
ality: $ \\lambda_2 \\leq \\phi(G) \\leq O(\\sqrt{\\lambda_2}) $. Here
$lambda_2$ is the second largest eigenvalue of the normalized Laplacian o
f $G$.\nThis is a special case of a more general inequality valid on Reima
nnian manifolds proven by Cheeger\, and was adapted to the discrete settin
g by Alon and Milman.\nWe shall see a proof of this inequality in the talk
\, and how it can be used to algorithmically generate a cut with a guarant
ee on sparsity as above.\n
URL:https://www.tcs.tifr.res.in/web/events/339
DTSTART;TZID=Asia/Kolkata:20130215T143000
DTEND;TZID=Asia/Kolkata:20130215T160000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR