5 citations · 12 across the 4 of their papers we have counts for
4 papers · 1 filter
Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)-Time Spectral Algorithm for Balanced Separator
Lorenzo Orecchia, Sushant Sachdeva, Nisheeth K. Vishnoi
We give a novel spectral approximation algorithm for the balanced separator problem that, given a graph G, a constant balance b \in (0,1/2], and a parameter γ, either finds an Ω(b)…
Towards an SDP-based Approach to Spectral Methods: A Nearly-Linear-Time Algorithm for Graph Partitioning and Decomposition
Lorenzo Orecchia, Nisheeth K. Vishnoi
In this paper, we consider the following graph partitioning problem: The input is an undirected graph a balance parameter and a target conductance value…
Implementing regularization implicitly via approximate eigenvector computation
Michael W. Mahoney, Lorenzo Orecchia
Regularization is a powerful technique for extracting useful information from noisy data. Typically, it is implemented by adding some sort of norm constraint to an objective functi…
A Local Spectral Method for Graphs: with Applications to Improving Graph Partitions and Exploring Data Graphs Locally
Michael W. Mahoney, Lorenzo Orecchia, Nisheeth K. Vishnoi
The second eigenvalue of the Laplacian matrix and its associated eigenvector are fundamental features of an undirected graph, and as such they have found widespread use in scientif…