A Reformulation of the Arora-Rao-Vazirani Structure Theorem

Sanjeev Arora, James Lee, Sushant Sachdeva

In a well-known paper[ARV], Arora, Rao and Vazirani obtained an O(sqrt(log n)) approximation to the Balanced Separator problem and Uniform Sparsest Cut. At the heart of their resul…