Rounding parallel repetitions of unique games

Boaz Barak, Moritz Hardt, Oded Regev, Ishay Haviv, Anup Rao, David Steurer

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

Abstract

We show a connection between the semidefinite relaxation of unique games and their behavior under parallel repetition. Specifically, denoting by val(G) the value of a two-prover unique game G, and by sdpval(G) the value of a natural semidefinite program to approximate val(G), we prove that for every ℓ ∈ N, if sdpval(G) ≥ 1 - δ, then Val(G) ≥ 1 - √sℓδ. Here, G denotes the ℓ-fold parallel repetition of G, and s = O(log(k/δ)), where k denotes the alphabet size of the game. For the special case where G is an XOR game (i.e., k = 2), we obtain the same bound but with s as an absolute constant. Our bounds on s are optimal up to a factor of O(log1/δ)). For games with a significant gap between the quantities val(G) and sdpval(G), our result implies that val(G) may be much larger than val(G), giving a counterexample to the strong parallel repetition conjecture. In a recent breakthrough, Raz (FOCS '08) has shown such an example using the max-cut game on odd cycles. Our results are based on a generalization of his techniques.

Original languageEnglish (US)
Title of host publicationProceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
Pages374-383
Number of pages10
DOIs
StatePublished - 2008
Event49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 - Philadelphia, PA, United States
Duration: Oct 25 2008Oct 28 2008

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
CountryUnited States
CityPhiladelphia, PA
Period10/25/0810/28/08

ASJC Scopus subject areas

  • Computer Science(all)

Cite this