Opening Spectral Graph Theory: Conductance and Sparsest-Cut
Spectral Graph Theory: Conductance and Sparsest-Cut
- Length
- 18 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Conductance and quadratic forms
Conductance and the sparsest-cut problem link a graph's bottlenecks to , the second smallest eigenvalue of its Laplacian. O'Donnell, in session 46 of CMU 15-750 (A Theorist's Toolkit), defines a vertex set's conductance as the probability that a random walk escapes it in one step. He rewrites that probability as the Laplacian quadratic form of an indicator function divided by its variance. Minimizing over 0–1 functions gives the NP-hard sparsest-cut problem, while minimizing over all real functions gives . Cheeger's inequality is stated without proof, and thresholding an eigenvector is sketched as the route to a low-conductance cut. Graph Laplacians, Rayleigh quotients and random walks are assumed.

Your comment is kept while you sign up.Sign in
Relaxes sparsest cut from 0–1 functions to real functions, turning an NP-hard minimum into .
Conductance and the sparsest-cut problem link a graph's bottlenecks to , the second smallest eigenvalue of its Laplacian. O'Donnell, in session 46 of CMU 15-750 (A Theorist's Toolkit), defines a vertex set's conductance as the probability that a random walk escapes it in one step. He rewrites that probability as the Laplacian quadratic form of an indicator function divided by its variance. Minimizing over 0–1 functions gives the NP-hard sparsest-cut problem, while minimizing over all real functions gives . Cheeger's inequality is stated without proof, and thresholding an eigenvector is sketched as the route to a low-conductance cut. Graph Laplacians, Rayleigh quotients and random walks are assumed.
This lecture
Lecture 46 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.