Analytical approach to parallel repetition

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.

Based on joint work with David Steurer.
See http://people.csail.mit.edu/madhu/reading-group/