Derandomized Parallel Repetition Theorems for Free Games

摘要

Raz’s parallel repetition theorem (SIAM J Comput 27(3):763–803, 1998) together with improvements of Holenstein (STOC, pp 411–419, 2007) shows that for any two-prover one-round game with value at most ({1- epsilon}) (for ({epsilon leq 1/2})), the value of the game repeated n times in parallel on independent inputs is at most ({(1- epsilon)^{Omega(frac{epsilon^2 n}{ell})}}), where ℓ is the answer length of the game. For free games (which are games in which the inputs to the two players are uniform and independent), the constant 2 can be replaced with 1 by a result of Barak et al. (APPROX-RANDOM, pp 352–365, 2009). Consequently, ({n=O(frac{t ell}{epsilon})}) repetitions suffice to reduce the value of a free game from ({1- epsilon}) to ({(1- epsilon)^t}), and denoting the input length of the game by m, it follows that ({nm=O(frac{t ell m}{epsilon})}) random bits can be used to prepare n independent inputs for the parallel repetition game.