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

Conference Object
Change log
Li, H 
Sun, H 
Zanetti, L 

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 = c_{ij} 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 I. We develop an \tilde{O}(kn^2) time algorithm that, for any (1-\eps)-satisfiable instance, produces an assignment satisfying a (1 - O(k)\sqrt{\eps})-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 (1- O(k^2)\eps)-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.

Spectral methods, Hermitian Laplacians, the Max-2-Lin problem, Unique Games
Journal Title
Leibniz International Proceedings in Informatics, LIPIcs
Conference Name
27th Annual European Symposium on Algorithms (ESA 2019)
Journal ISSN
Volume Title
Schloss Dagstuhl--Leibniz-Zentrum für Informatik
European Research Council (679660)