@inproceedings{e6c7d8a45db0407197f9f0c99792e5b4,

title = "Unique games on expanding constraint graphs are easy",

abstract = "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.",

keywords = "Approximation algorithms, Expander graphs, Semidehmte programming",

author = "Sanjeev Arora and David Steurer and Knot, {Subhash A.} and Madhur Tulsiani and Alexandra Kolla and Vishnoi, {Nisheeth K.}",

year = "2008",

doi = "10.1145/1374376.1374380",

language = "English (US)",

isbn = "9781605580470",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "21--28",

booktitle = "STOC'08",

note = "40th Annual ACM Symposium on Theory of Computing, STOC 2008 ; Conference date: 17-05-2008 Through 20-05-2008",

}