Improved rounding for parallel repeated unique games

RANDOM 2010.

PDF

abstract

We show a tight relation between the behavior of unique games under parallel repetition and their semidefinite value. Let $G$ be a unique game with alphabet size $k$. Suppose the semidefinite value of $G$, denoted $sdp(G)$, is at least $1-\varepsilon$. Then, we show that the optimal value $opt(G^\ell)$ of the $\ell$-fold repetition of $G$ is at least $1-O(\sqrt{\ell \varepsilon \log k})$. This bound confirms a conjecture of Barak et al. (FOCS 2008), who showed a lower bound that was worse by $\sqrt{\ell\varepsilon\log (\frac1\varepsilon)}$.

A consequence of our bound is the following tight relation between the semidefinite value of $G$ and the amortized value $\overline{opt}(G):= \sup_{\ell\in\mathbb N} opt(G^\ell)^{1/\ell}$, $$sdp(G)^{O(\log k)} \le \overline{opt}(G) \le sdp(G).$$ The proof closely follows the approach of Barak et al. (2008).

Our technical contribution is a natural orthogonalization procedure for nonnegative functions. The procedure has the property that it preserves distances up to an absolute constant factor. In particular, our orthogonalization avoids the additive increase in distances caused by the truncation step of Barak et al. (2008).