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

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 languageEnglish (US)
Title of host publicationSTOC'08
Subtitle of host publicationProceedings of the 2008 ACM Symposium on Theory of Computing
Pages21-28
Number of pages8
StatePublished - Dec 8 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

Other

Other40th Annual ACM Symposium on Theory of Computing, STOC 2008
CountryCanada
CityVictoria, BC
Period5/17/085/20/08

Keywords

  • Approximation algorithms
  • Expander graphs
  • Semidehmte programming

ASJC Scopus subject areas

  • Software

Cite this

Arora, S., Steurer, D., Knot, S. A., Tulsiani, M., Kolla, A., & Vishnoi, N. K. (2008). Unique games on expanding constraint graphs are easy. In STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing (pp. 21-28). (Proceedings of the Annual ACM Symposium on Theory of Computing).

Unique games on expanding constraint graphs are easy. / Arora, Sanjeev; Steurer, David; Knot, Subhash A.; Tulsiani, Madhur; Kolla, Alexandra; Vishnoi, Nisheeth K.

STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing. 2008. p. 21-28 (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

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, pp. 21-28, 40th Annual ACM Symposium on Theory of Computing, STOC 2008, Victoria, BC, Canada, 5/17/08.
Arora S, Steurer D, Knot SA, Tulsiani M, Kolla A, Vishnoi NK. Unique games on expanding constraint graphs are easy. In STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing. 2008. p. 21-28. (Proceedings of the Annual ACM Symposium on Theory of Computing).
Arora, Sanjeev ; Steurer, David ; Knot, Subhash A. ; Tulsiani, Madhur ; Kolla, Alexandra ; Vishnoi, Nisheeth K. / Unique games on expanding constraint graphs are easy. STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing. 2008. pp. 21-28 (Proceedings of the Annual ACM Symposium on Theory of Computing).
@inproceedings{59af20393faf4a46bbfd5149a359898b,
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",
month = "12",
day = "8",
language = "English (US)",
isbn = "9781605580470",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
pages = "21--28",
booktitle = "STOC'08",

}

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/12/8

Y1 - 2008/12/8

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

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

ER -