Irit Dinur

Weizmann Institute; Radcliffe institute

April 15, 2013

We propose an “analytical” framework for studying parallel repetitions of one-round two-prover games. We define a new relaxation of the value of a game, val+, and prove that it is both multiplicative and a good approximation for the true value of the game. These two properties imply Raz's parallel repetition theorem as

$val(G^k) ~ val+(G^k) = val+(G)^k ~ val(G)^k$

Using this approach, we will describe a reasonably simple proof for the NP-hardness for $label-cover(1,delta)$, the starting point of many inapproximability results.

We also discuss some new results, including

* parallel repetition for small-soundness games

* a new reduction from general to projection games

* a tight bound for few repetitions matching Raz's counterexample.