Time+Place: Thursday 08/01/2015 12:30 Room 337-8 Taub Bld.
Title: Parallel Repetition From Fortification
Speaker: Dana Moshkovitz - Colloquium Lecture - Note: UNUSUAL TIME http://people.csail.mit.edu/dmoshkov/
Affiliation: Computer Science, M I T
Host: Eli Ben-Sasson


The Parallel Repetition Theorem upper-bounds the value of a repeated
(tensored) two prover game in terms of the value of the base game and the
number of repetitions.
In this work we give a simple transformation on games -- "fortification" --
and show that for fortified games, the value of the repeated game decreases
perfectly exponentially with the number of repetitions, up to an arbitrarily
small additive error. Our proof is combinatorial and (very) short.

As corollaries, we obtain:

(1) Starting from a PCP Theorem with soundness error bounded away from 1, we
get a PCP with arbitrarily small constant soundness error. In particular,
starting with the combinatorial PCP of Dinur, we get a combinatorial PCP
with low error. The latter can be used for hardness of approximation as in
the work of Hastad.

(2) Starting from the work of the author and Raz, we get a projection PCP
theorem with the smallest soundness error known today. The theorem yields
nearly a quadratic improvement in the size compared to previous work.

Short Bio:

Dana Moshkovitz is an assistant professor of Computer Science at MIT.
Her research is in Theoretical Computer Science, and much of it focuses on
the limitations of approximation algorithms and probabilistic checking of

Dana did her PhD at the Weizmann Institute in Israel.
Her thesis co-won the Nessyahu Prize for best math PhD thesis in Israel in
2009, and part of this work was awarded the FOCS 2008 Best paper.
Dana spent a couple of years at Princeton University and the Institute of
Advanced Study before joining MIT in the end of 2010.
She is the recipient of MIT's Jerome Saltzer teaching award.

Refreshments will be served from 12:15
Lecture starts at 12:30