  This paper ties the line of work on algorithms that find an
O(sqrt(log(n)))-approximation to the sparsest cut together with the line of
work on algorithms that run in sub-quadratic time by using only
single-commodity flows. We present an algorithm that simultaneously achieves
both goals, finding an O(sqrt(log(n)/eps))-approximation using O(n^eps log^O(1)
n) max-flows. The core of the algorithm is a stronger, algorithmic version of
Arora et al.'s structure theorem, where we show that matching-chaining argument
at the heart of their proof can be viewed as an algorithm that finds good
augmenting paths in certain geometric multicommodity flow networks. By using
that specialized algorithm in place of a black-box solver, we are able to solve
those instances much more efficiently. We also show the cut-matching game
framework can not achieve an approximation any better than Omega(log(n)/log
log(n)) without re-routing flow.
