Improved rounding for parallel repeated unique games

RANDOM 2010.



We show a tight relation between the behavior of unique games under parallel repetition and their semidefinite value. Let GG be a unique game with alphabet size kk. Suppose the semidefinite value of GG, denoted sdp(G)sdp(G), is at least 1ε1-\varepsilon. Then, we show that the optimal value opt(G)opt(G^\ell) of the \ell-fold repetition of GG is at least 1O(εlogk)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 εlog(1ε)\sqrt{\ell\varepsilon\log (\frac1\varepsilon)}.

A consequence of our bound is the following tight relation between the semidefinite value of GG and the amortized value opt(G):=supNopt(G)1/\overline{opt}(G):= \sup_{\ell\in\mathbb N} opt(G^\ell)^{1/\ell}, sdp(G)O(logk)opt(G)sdp(G). 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).