PARALLEL REPETITION FROM FORTIFICATION

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, hjones01@csail.mit.edu

Relevant URL: http://toc.csail.mit.edu/node/570

Speaker URL: None

Speaker Photo:
None

Reminders to: theory-seminars@csail.mit.edu, toc@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: 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.

Research Areas:

Impact Areas:

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

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