Computer Science/Discrete Mathematics Seminar I

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.