Spectral algorithms for unique games

Alexandra Kolla

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

Abstract

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
Pages122-130
Number of pages9
DOIs
StatePublished - Aug 10 2010
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

Other

Other25th Annual IEEE Conference on Computational Complexity, CCC 2010
CountryUnited States
CityCambridge, MA
Period6/9/106/11/10

Keywords

  • Approximation algorithms
  • Spectral techniques
  • Unique games

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

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

  • Cite this

    Kolla, A. (2010). Spectral algorithms for unique games. In Proceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010 (pp. 122-130). [5497894] (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2010.20