Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-021 | 2nd March 2009 00:00

How to Play Unique Games on Expanders

RSS-Feed




TR09-021
Authors: Konstantin Makarychev, Yury Makarychev
Publication: 19th March 2009 10:39
Downloads: 3763
Keywords: 


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 assignments satisfying at least a (1 - C epsilon/h) fraction of all constraints if epsilon < c lambda where h is the edge expansion of G, lambda is the second smallest eigenvalue of the Laplacian of G, and C and c are some absolute constants.



ISSN 1433-8092 | Imprint