Conductance (Randomized algorithms, Fall 2022, Lecture 20)
Kent Quanrud · 74:20
Cheeger’s inequality sandwiches a graph’s conductance Φ between λ₂/2 and √(2λ₂) of the normalized Laplacian, so a combinatorial “how balanced is the thinnest cut” quantity controls (lazy) random-walk mixing and also y...