Parallel Repetition From Fortification
Tuesday, May 13, 2014 - 4:15pm to 5:15pm
Refreshments:
32-G449 at 3:45pm
Location:
32-G449
Speaker:
Dana Moshkovitz, MIT
Abstract: The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game G^k in terms of the value of the game G and the number of repetitions k.
Contrary to what one might have guessed, the value of G^k is not val(G)^k, but rather a more complicated expression depending on properties of G.
In this work we give a simple transformation, "fortification", that was inspired by combinatorial constructions of error correcting codes, and can be applied to games of interest. We show that for fortified games G, the value of the k-repeated game is approximately val(G)^k.
Unlike previous proofs of the parallel repetition theorem that relied on information theory or linear algebra, our proof is purely combinatorial and quite short.
In this work we give a simple transformation, "fortification", that was inspired by combinatorial constructions of error correcting codes, and can be applied to games of interest. We show that for fortified games G, the value of the k-repeated game is approximately val(G)^k.
Unlike previous proofs of the parallel repetition theorem that relied on information theory or linear algebra, our proof is purely combinatorial and quite short.
The proof can be used to transform a basic PCP theorem (e.g., obtained from Dinur's proof) to a low error PCP theorem as needed for hardness of approximation (e.g., Hastad's results). It can also be used to derive a projection PCP theorem with the lowest error known today.