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 proofs. 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