期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
