Analytical Approach to Parallel Repetition

by Irit Dinur and David Steurer

Oded's comments

This paper provides improved results for parallel repetition of projection games. The results are tighter than those known before, and in particular they can handle (relatively) well the case that the value of the game is very small (i.e., very close to zero) or very large (i.e., very close to one); cf. Thms 1.1 and 1.4, resp. In addition, they handle well the case of different games. All these are a consequence of working with a relaxation, which, on the one hand, approximates the actual value relatively well and, on the other hand, lends itself to the analysis of the effect of parallel repetitions.

Unfortunately, the technical parts of the paper (starting with Sec. 2) are not friendly enough towards non-experts.

The original abstract

We propose an analytical framework for studying parallel repetition, a basic product operation for one-round two-player games. In this framework, we consider a relaxation of the value of a game, $\mathrm{val}_+$, and prove that for projection games, it is both multiplicative (under parallel repetition) and a good approximation for the true value. These two properties imply a parallel repetition bound as
$$ \mathrm{val}(G^{\otimes k}) \approx \mathrm{val}_+(G^{\otimes k}) = \mathrm{val}_+(G)^{k} \approx \mathrm{val}(G)^{k}. $$

Using this framework, we can also give a short proof for the NP-hardness of Label-Cover$(1,\delta)$ for all $\delta>0$, starting from the basic PCP theorem. We prove the following new results:

Our techniques also allow us to bound the value of the direct product of multiple games, namely, a bound on $\mathrm{val}(G_1\otimes ...\otimes G_k)$ for different projection games $G_1,...,G_k$.

See arXiv:1305.1979.


Back to list of Oded's choices.