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(Gk) val+(Gk)=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.
Date
Speakers
Irit Dinur
Affiliation
Weizmann Institute; Radcliffe institute