Hermitian Laplacians and a Cheeger inequality for the Max-2-Lin problem

Abstract

We study spectral approaches for the MAX-2-LIN(k) problem, in which we are given a system of $m$ linear equations of the form $x_i-x_j\equiv c_{ij}\mathrm{mod}k$, and required to find an assignment to the $n$ variables $\{x_i\}$ that maximises the total number of satisfied equations. We consider Hermitian Laplacians related to this problem, and prove a Cheeger inequality that relates the smallest eigenvalue of a Hermitian Laplacian to the maximum number of satisfied equations of a MAX-2-LIN(k) instance $\mathcal{I}$. We develop an $\tilde{O}(k{n}^2)$ time algorithm that, for any $(1-\epsilon )$-satisfiable instance, produces an assignment satisfying a $\left(1-O(k)\sqrt{\epsilon }\right)$-fraction of equations. We also present a subquadratic-time algorithm that, when the graph associated with $\mathcal{I}$ is an expander, produces an assignment satisfying a $\left(1-O(k^2)\epsilon \right)$-fraction of the equations. Our Cheeger inequality and first algorithm can be seen as generalisations of the Cheeger inequality and algorithm for MAX-CUT developed by Trevisan.