Speaker: Dana Moshkovitz

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

Public: Yes

Location: 32-G449

Event Type:

Room Description:

Host: Vinod Vaikuntanathan, CIS, TOC, CSAIL, MIT

Contact: Holly A Jones,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,,


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.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation Colloquium - 2014.

Created by Holly A Jones Email at Tuesday, May 06, 2014 at 2:23 PM.