17 citations · 22 across the 4 of their papers we have counts for
4 papers
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…
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…
A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues
Shayan Oveis Gharan, Luca Trevisan
We prove that the diameter of any unweighted connected graph G is O(k log n/lambda_k), for any k>= 2. Here, lambda_k is the k smallest eigenvalue of the normalized laplacian of G.…
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
Shayan Oveis Gharan, Luca Trevisan
Kolla and Tulsiani [KT07,Kolla11} and Arora, Barak and Steurer [ABS10] introduced the technique of subspace enumeration, which gives approximation algorithms for graph problems suc…