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

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 … Read more

A Spectral Algorithm for Improving Graph Partitions

In the cut-improvement problem, we are asked, given a starting cut (T,V\T) in a graph G, to find a cut with low conductance around(T, V\T) or produce a certificate that there is none. More precisely, for a notion of correlation between cuts, cut-improvement algorithms seek to produce approximation guarantees of the following form: for any … Read more