Rounding parallel repetitions of Unique Games

with Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev. FOCS 2008.



We show a connection between the semidefinite relaxation of unique games and their behavior under parallel repetition. Specifically, denoting by val(G)\mathrm{val}(G) the value of a two-prover unique game GG, and by sdp(G)\mathrm{sdp}(G) the value of a natural semidefinite program to approximate val(G)\mathrm{val}(G), we prove that for every N\ell\in\mathbb{N}, if sdp(G)1δ\mathrm{sdp}(G) \geq 1-\delta, then val(G)1sδ.\mathrm{val}(G^{\ell}) \geq 1 - \sqrt{s\ell\delta}. Here, GG^{\ell} denotes the \ell-fold parallel repetition of GG, and s=O(log(k/δ))s=O(\log( k/\delta)), where kk denotes the alphabet size of the game. For the special case where GG is an XOR game (i.e., k=2k=2), we obtain the same bound but with ss as an absolute constant. Our bounds on ss are optimal up to a factor of O(log(1/δ))O(\log(1/ \delta)).

For games with a significant gap between the quantities val(G)\mathrm{val}(G) and sdp(G)\mathrm{sdp}(G), our result implies that val(G)\mathrm{val}(G^{\ell}) may be much larger than val(G)\mathrm{val}(G)^{\ell}, 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.


  • Unique Games Conjecture
  • semidefinite programming