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)…