17 citations · 19 across the 17 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.DS2015
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…
cs.DS2015
Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee
We prove two generalizations of the Cheeger's inequality. The first generalization relates the second eigenvalue to the edge expansion and the vertex expansion of the graph G, $λ_2…