Unique Games on expanding constraints graphs are easy

with Sanjeev Arora, Subhash Khot, Alexandra Kolla, Madhur Tulsiani, Nisheeth Vishnoi. STOC 2008.

abstract

We present an efficient algorithm to find a good solution to the Unique Games problem when the constraint graph is an expander.

We introduce a new analysis of the standard SDP in this case that involves correlations among distant vertices. It also leads to a parallel repetition theorem for unique games when the graph is an expander.

keywords

Unique Games Conjecture
eigenvalues
semidefinite programming
approximation algorithms