18 citations · 66 across the 15 of their papers we have counts for
Showing 2012Show all
3 papers · 1 filter
cs.DM2012★ 1 cited
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.…
cs.DS2012★ 1 cited
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…
cs.CC2012
Better Pseudorandom Generators from Milder Pseudorandom Restrictions
Parikshit Gopalan, Raghu Meka, Omer Reingold +2
We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pse…