O( p logn) approximation to SPARSEST CUT can be found in
Sanjeev Arora, Elad Hazan, Satyen Kale · 2004
We show that the recent results for obtaining O( p logn)-approximation to sparsest cut and bal- anced separator problems due to Arora, Rao, and Vazirani (2004) can be used to derive an ~ O(n 2 ) time approximation algorithm for an n-node graph. The previous best algorithm needed to solve a semideflnite program with O(n 3 ) constraints. Our algorithm relies on e-ciently flnding expander ∞ows in the graph. The existence of these ∞ows was established by (ARV).