TY - GEN

T1 - Rounding parallel repetitions of unique games

AU - Barak, Boaz

AU - Hardt, Moritz

AU - Regev, Oded

AU - Haviv, Ishay

AU - Rao, Anup

AU - Steurer, David

PY - 2008

Y1 - 2008

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

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

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

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

U2 - 10.1109/FOCS.2008.55

DO - 10.1109/FOCS.2008.55

M3 - Conference contribution

AN - SCOPUS:57949103885

SN - 9780769534367

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 374

EP - 383

BT - Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008

T2 - 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008

Y2 - 25 October 2008 through 28 October 2008

ER -