Content area
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 Conjecture. We design an \(O(1)\)-approximation algorithm to Sparsest Cut for the class of Cayley graphs over Abelian groups, running in time \(n^{O(1)}\cdot \exp\{d^{O(d)}\}\) where \(d\) is the degree of the graph. Previous work has centered on solving cut problems on graphs which are ``expander-like'' in various senses, such as being a small-set expander or having low threshold rank. In contrast, low-degree Abelian Cayley graphs are natural examples of non-expanding graphs far from these assumptions (e.g. the cycle). We demonstrate that spectral and semidefinite programming-based methods can still succeed in these graphs by analyzing an eigenspace enumeration algorithm which searches for a sparse cut among the low eigenspace of the Laplacian matrix. We dually interpret this algorithm as searching for a hyperplane cut in a low-dimensional embedding of the graph. In order to analyze the algorithm, we prove a bound of \(d^{O(d)}\) on the number of eigenvalues ``near'' \(\lambda_2\) for connected degree-\(d\) Abelian Cayley graphs. We obtain a tight bound of \(2^{\Theta(d)}\) on the multiplicity of \(\lambda_2\) itself which improves on a previous bound of \(2^{O(d^2)}\) by Lee and Makarychev.