Random Walks and Evolving Sets: Faster Convergences and Limitations
Refereed conference paper presented and published in conference proceedings

Times Cited
Altmetrics Information

Other information
AbstractAnalyzing the mixing time of random walks is a well- studied problem with applications in random sampling and more recently in graph partitioning. In this work, we present new analysis of random walks and evolving sets using more combinatorial graph structures, and show some implications in approximating small-set expansion. On the other hand, we provide examples showing the limitations of using random walks and evolving sets in disproving the small-set expansion hypothesis.

1. We define a combinatorial analog of the spectral gap, and use it to prove the convergence of non- lazy random walks. A corollary is a tight lower bound on the small-set expansion of graph powers for any graph.
2. We prove that random walks converge faster when the robust vertex expansion of the graph is larger. This provides an improved analysis of the local graph partitioning algorithm using the evolving set process, and also derives an alternative proof of an improved Cheeger's inequality.
3. We give an example showing that the evolving set process fails to disprove the small-set expansion hypothesis. This refutes a conjecture of Oveis Gharan and shows the limitations of all existing local graph partitioning algorithms in approximating small-set expansion.
All Author(s) ListSiu On Chan, Tsz Chiu Kwok, Lap Chi Lau
Name of ConferenceSymposium on Discrete Algorithms
Start Date of Conference16/01/2017
End Date of Conference19/01/2017
Place of ConferenceBarcelona
Country/Region of ConferenceSpain
Proceedings TitleProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
LanguagesEnglish-United States

Last updated on 2021-25-01 at 00:32