Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)-Time Spectral Algorithm for Balanced Separator

Understand

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 \gamma, either finds an \Omega(b)-balanced cut of conductance O(\sqrt(\gamma)) in G, or outputs a certificate that all b-balanced cuts in G have conductance at least \gamma, and runs in time \tilde{O}(m).

• This settles the question of designing asymptotically optimal spectral algorithms for balanced separator.
• Our algorithm relies on a variant of the heat kernel random walk and requires, as a subroutine, an algorithm to compute \exp(-L)v where L is the Laplacian of a graph related to G and v is a vector.
• Algorithms for computing the matrix-exponential-vector product efficiently comprise our next set of results.