PARALLEL REPETITION FROM FORTIFICATION
Date: Tuesday, May 13, 2014
Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone
Refreshments: 3:45 PM
Host: Vinod Vaikuntanathan, CIS, TOC, CSAIL, MIT
Contact: Holly A Jones, email@example.com
Relevant URL: http://toc.csail.mit.edu/node/570
Speaker URL: None
firstname.lastname@example.org, email@example.com, firstname.lastname@example.org
TALK: PARALLEL REPETITION FROM FORTIFICATION
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.
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.
Created by Holly A Jones at Tuesday, May 06, 2014 at 2:23 PM.