Spectral algorithms for unique games

Alexandra Kolla

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We present a new algorithm for Unique Games which is based on purely 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 Label-Extended graph associated with the instance of Unique Games. In particular, we show how our techniques imply a quasipolynomial time algorithm that decides satisfiability of a game on the Khot-Vishnoi [14] integrality gap instance. Notably, when run on that instance, the standard SDP relaxation of Unique Games 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 [2]) and a sub-exponential time algorithm for Unique Games on the Hypercube.

Original languageEnglish (US)
Title of host publicationProceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010
Number of pages9
StatePublished - 2010
Externally publishedYes
Event25th Annual IEEE Conference on Computational Complexity, CCC 2010 - Cambridge, MA, United States
Duration: Jun 9 2010Jun 11 2010

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159


Other25th Annual IEEE Conference on Computational Complexity, CCC 2010
Country/TerritoryUnited States
CityCambridge, MA


  • Approximation algorithms
  • Spectral techniques
  • Unique games

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Computational Mathematics


Dive into the research topics of 'Spectral algorithms for unique games'. Together they form a unique fingerprint.

Cite this