Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-029 | 3rd March 2010 21:25

Spectral Algorithms for Unique Games


Authors: Alexandra Kolla
Publication: 4th March 2010 11:36
Downloads: 3318


We present a new algorithm for Unique Games which is based on purely {\em spectral} techniques, in contrast to previous
work in the area, which relies heavily on semidefinite programming (SDP). Given a highly satisfiable instance of Unique Games, our algorithm is able to recover a good assignment.
The approximation guarantee depends only on the completeness of the game, and not on the alphabet size,
while the running time depends on spectral properties of the {\em Label-Extended} graph associated with the instance of Unique Games.\\
In particular, we show how our techniques imply a quasi-polynomial time
algorithm that decides satisfiability of a game on the Khot-Vishnoi(~\cite{KV}) integrality gap instance. Notably, when run on that instance, the standard SDP relaxation of Unique
Games {\em fails}. As a special case, we also show how to re-derive a polynomial time algorithm for Unique Games on
expander constraint graphs (similar to~\cite{AKKTSV}) and a sub-exponential time algorithm for Unique Games on the Hypercube.

ISSN 1433-8092 | Imprint