---
abstract: |
    We study spectral approaches for the  problem, in which we are given a system of $m$ linear equations of the form $
    x_i - x_j \equiv {c}_{ij}{\hspace{-5pt}\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  instance ${\mathcal{I}}$. We develop an $\widetilde{O}(kn^2)$ time[^1] algorithm that, for any $(1-{\varepsilon})$-satisfiable instance, produces an assignment satisfying a $\left(1 - O(k)\sqrt{{\varepsilon}}\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){\varepsilon}\right)$-fraction of the equations. Our Cheeger inequality and first algorithm can be seen as generalisations of the Cheeger inequality and algorithm for developed by Trevisan.
author:
- 'Huan Li[^2]'
- 'He Sun[^3]'
- 'Luca Zanetti[^4]'
bibliography:
- 'references.bib'
title: |
    Hermitian Laplacians and a Cheeger inequality\
    for the Max-2-Lin problem\[sec:preliminaries\]
---

#### Acknowledgement.

The project is partially supported by the ERC Starting Grant (DYNAMIC MARCH). We are very grateful to Mihai Cucuringu for valuable discussions on Hermitian Laplacian matrices and their applications. We would also like to thank Chris Heunen for some fruitful conversations on topics closely related to this paper.

[^1]: The notation $\widetilde{O}(\cdot)$ suppresses poly-logarithmic factors in $n$, $m$, and $k$.

[^2]: School of Computer Science, Fudan University, China

[^3]: School of Informatics, the University of Edinburgh, UK

[^4]: Department of Computer Science and Technology, the University of Cambridge, UK
