# Rounding parallel repetitions of Unique Games

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

PDF

## 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