Random Walks and Evolving Sets: Faster Convergences and Limitations

Siu On Chan, Tsz Chiu Kwok, Lap Chi Lau

Analyzing 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 analy…