Sparsest Cut on Abelian Cayley GraphsResearch Paper
The sparsest cut problem asks for a set of vertices of a graph that is poorly connected to the rest. It is NP-hard to solve exactly, and the best polynomial-time guarantee for general graphs remains the approximation of Arora, Rao and Vazirani (ARV09); no subexponential-time constant-factor approximation is known for general graphs. This…