How to Play Unique Games on Expanders

Abstract

In this note we improve a recent result by Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi on solving the Unique Games problem on expanders. Given a $(1-\epsilon )$-satisfiable instance of Unique Games with the constraint graph $G$, our algorithm finds an assignment satisfying at least a $1-C\epsilon /h_G$ fraction of all constraints if $\epsilon <c{\lambda }_G$ where $h_G$ is the edge expansion of $G$, ${\lambda }_G$ is the second smallest eigenvalue of the Laplacian of $G$, and $C$ and $c$ are some absolute constants.