### 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 |

Pages | 21-28 |

Number of pages | 8 |

State | Published - Dec 8 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 | Canada |

City | Victoria, BC |

Period | 5/17/08 → 5/20/08 |

### Keywords

- Approximation algorithms
- Expander graphs
- Semidehmte programming

### ASJC Scopus subject areas

- Software

### Cite this

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

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

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

}

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 -