Parallel Repetition From Fortification
Event details
| Date | 16.01.2015 |
| Hour | 14:00 › 15:00 |
| Speaker | Dana Moshkovitz, MIT |
| Location | |
| Category | Conferences - Seminars |
Abstract:
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 short.
As corollaries, we obtain simple combinatorial proofs of state-of-the-art PCP Theorems.
Short Bio:
Dana is an assistant professor at the Electrical Engineering and Computer Science department of MIT and a member of CSAIL. She is a part of the theory of computation group. She has a broad interest in Theoretical Computer Science, with a focus on Probabilistically Checkable Proofs (PCP), Pseudo-randomness, Coding theory and Algorithms.
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 short.
As corollaries, we obtain simple combinatorial proofs of state-of-the-art PCP Theorems.
Short Bio:
Dana is an assistant professor at the Electrical Engineering and Computer Science department of MIT and a member of CSAIL. She is a part of the theory of computation group. She has a broad interest in Theoretical Computer Science, with a focus on Probabilistically Checkable Proofs (PCP), Pseudo-randomness, Coding theory and Algorithms.
Practical information
- Informed public
- Free
Organizer
- Nisheeth Vishnoi