Cheeger's Inequality and Evolving Sets

I will present a new proof of Cheeger's inequality, which can be generalized to incorporate robust vertex expansion in it. The proof builds on the ideas of Lovasz and Kannan for analyzing mixing times of random walks. I will also discuss similar analyses for different local graph partitioning algorithms (random walks, pagerank, evolving sets). Finally, I will present an example showing the limitations of local graph partitioning algorithms in attacking the small-set expansion hypothesis, disproving a conjecture by Oveis Gharan about evolving sets.

Joint work with Siu On Chan, Tsz Chiu Kwok, and Yin Tat Lee.