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

Huan Li, He Sun, Luca Zanetti

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…