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

arXiv: https://arxiv.org/abs/1811.10909 · HTML: https://mlsanity.com/paper/1811.10909/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2018.

## Built on by (most cited first, 3 of 3)

- [Hierarchical Clustering: O(1)-Approximation for Well-Clustered Graphs](https://mlsanity.com/paper/2112.09055/) (2021)
- [Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues](https://mlsanity.com/paper/2211.09776/) (2022)
- [An Improved and Generalised Analysis for Spectral Clustering](https://mlsanity.com/paper/2511.23261/) (2025)

## Abstract (arXiv)

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 xi - xj equiv cijmod k, and required to find an assignment to the n variables xi 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 I. We develop an widetildeO(kn2) time algorithm that, for any (1-varepsilon)-satisfiable instance, produces an assignment satisfying a left(1 - O(k)√varepsilonright)-fraction of equations. We also present a subquadratic-time algorithm that, when the graph associated with I is an expander, produces an assignment satisfying a left(1- O(k2)varepsilon 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.