Unique games on expanding constraint graphs are easy

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

doi:10.1145/1374376.1374380

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 proceeding › Conference contribution

75 Scopus citations

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.

Original language	English (US)
Title of host publication	STOC'08
Subtitle of host publication	Proceedings of the 2008 ACM Symposium on Theory of Computing
Publisher	Association for Computing Machinery
Pages	21-28
Number of pages	8
ISBN (Print)	9781605580470
DOIs	https://doi.org/10.1145/1374376.1374380
State	Published - 2008
Event	40th Annual ACM Symposium on Theory of Computing, STOC 2008 - Victoria, BC, Canada Duration: May 17 2008 → May 20 2008

Publication series

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

Other

Other	40th Annual ACM Symposium on Theory of Computing, STOC 2008
Country/Territory	Canada
City	Victoria, BC
Period	5/17/08 → 5/20/08

All Science Journal Classification (ASJC) codes

Software

Keywords

Approximation algorithms
Expander graphs
Semidehmte programming

Access to Document

10.1145/1374376.1374380

Cite this

@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",

}

Arora, S, Steurer, D, Knot, SA, Tulsiani, M, Kolla, A & Vishnoi, NK 2008, Unique games on expanding constraint graphs are easy. in STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 21-28, 40th Annual ACM Symposium on Theory of Computing, STOC 2008, Victoria, BC, Canada, 5/17/08. https://doi.org/10.1145/1374376.1374380

Unique games on expanding constraint graphs are easy. / Arora, Sanjeev; Steurer, David; Knot, Subhash A. et al.
STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing. Association for Computing Machinery, 2008. p. 21-28 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Unique games on expanding constraint graphs are easy

AU - Arora, Sanjeev

AU - Steurer, David

AU - Knot, Subhash A.

AU - Tulsiani, Madhur

AU - Kolla, Alexandra

AU - Vishnoi, Nisheeth K.

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Expander graphs

KW - Semidehmte programming

UR - http://www.scopus.com/inward/record.url?scp=57049107485&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57049107485&partnerID=8YFLogxK

U2 - 10.1145/1374376.1374380

DO - 10.1145/1374376.1374380

M3 - Conference contribution

AN - SCOPUS:57049107485

SN - 9781605580470

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 21

EP - 28

BT - STOC'08

PB - Association for Computing Machinery

T2 - 40th Annual ACM Symposium on Theory of Computing, STOC 2008

Y2 - 17 May 2008 through 20 May 2008

ER -

Unique games on expanding constraint graphs are easy

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this