Rounding parallel repetitions of Unique Games

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

abstract

We show a connection between the semidefinite relaxation of unique games and their behavior under parallel repetition. Specifically, denoting by $\mathrm{val}(G)$ the value of a two-prover unique game $G$ , and by $\mathrm{sdp}(G)$ the value of a natural semidefinite program to approximate $\mathrm{val}(G)$ , we prove that for every $\ell\in\mathbb{N}$ , if $\mathrm{sdp}(G) \geq 1-\delta$ , then $\mathrm{val}(G^{\ell}) \geq 1 - \sqrt{s\ell\delta}.$ Here, $G^{\ell}$ denotes the $\ell$ -fold parallel repetition of $G$ , and $s=O(\log( k/\delta))$ , 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(\log(1/ \delta))$ .

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

keywords

Unique Games Conjecture
semidefinite programming