17 citations · 97 across the 38 of their papers we have counts for
Showing 2013Show all
3 papers · 1 filter
cs.DS2013
Partitioning into Expanders
Shayan Oveis Gharan, Luca Trevisan
Let G=(V,E) be an undirected graph, lambda_k be the k-th smallest eigenvalue of the normalized laplacian matrix of G. There is a basic fact in algebraic graph theory that lambda_k…
cs.DS2013★ 3 cited
Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank
Shayan Oveis Gharan, Luca Trevisan
We prove a structure theorem for the feasible solutions of the Arora-Rao-Vazirani SDP relaxation on low threshold rank graphs and on small-set expanders. We show that if G is a gra…
cs.DS2013★ 17 cited
Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee +2
Let ϕ(G) be the minimum conductance of an undirected graph G, and let 0=λ_1 <= λ_2 <=... <= λ_n <= 2 be the eigenvalues of the normalized Laplacian matrix of G. We prove that for a…