The Taub Faculty of Computer Science Events and Talks

We show a connection between the semi-definite 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 semi-definite program to approximate val(G), we prove that for every large enough $\ell$, if sdpval(G) is at least $1-\delta$, then the value of the $\ell$-times parallel repeated version of G is at least $sdpval(G)^{s \ell}$ where $s=O(\log(k/\delta))$ for general unique games and $s=O(1)$ for XOR games (i.e., k=2). By a result of Feige and Lovasz (STOC '92), our bounds are tight up to a factor of $O(\log(1/\delta))$ in the exponent. For games where there is a significant gap between the quantities val(G) and sdpval(G), our result implies that $val(G^{\ell})$ may be much larger than $\val(G)^{\ell}$, giving a counterexample to the strong parallel repetition conjecture. In a recent breakthrough, Raz has showed such an example using the max-cut game on odd cycles. Our results are based on a generalization of his techniques.

Joint work with Boaz Barak, Moritz Hardt, Anup Rao, Oded Regev and David Steurer.