How to Play Unique Games on Expanders

摘要

In this paper, we improve a result by Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi on solving the Unique Games problem on expanders. Given a (1 - ε)-satisfiable instance of Unique Games with the constraint graph G, our algorithm finds an assignment satisfying at least a 1 - Cε/h_G fraction of all constraints if ε