Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs

Tommaso d'Orsi, Chris Jones, Jake Ruotolo +2

Whether or not the Sparsest Cut problem admits an efficient $O(1)$-approximation algorithm is a fundamental algorithmic question with connections to geometry and the Unique Games C…