Unique games on expanding constraint graphs are easy

Sanjeev Arora, David Steurer, Subhash A. Knot, Madhur Tulsiani, Alexandra Kolla, Nisheeth K. Vishnoi

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

73 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationSTOC'08
Subtitle of host publicationProceedings of the 2008 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Number of pages8
ISBN (Print)9781605580470
StatePublished - 2008
Event40th Annual ACM Symposium on Theory of Computing, STOC 2008 - Victoria, BC, Canada
Duration: May 17 2008May 20 2008

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Other40th Annual ACM Symposium on Theory of Computing, STOC 2008
CityVictoria, BC

All Science Journal Classification (ASJC) codes

  • Software


  • Approximation algorithms
  • Expander graphs
  • Semidehmte programming

Cite this