Analytical Approach to Parallel Repetition
| Computer Science/Discrete Mathematics Seminar I | |
| Topic: | Analytical Approach to Parallel Repetition |
| Speaker: | Irit Dinur |
| Affiliation: | Weizmann Institute; Radcliffe institute |
| Date: | Monday, April 15 |
| Time/Room: | 11:15am - 12:15pm/S-101 |
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.