Computer Science/Discrete Mathematics Seminar II
On the Parallel Repetition Theorem
The Parallel Repetition Theorem by Raz is used to amplify the soundness of PCP's, and is one of the ingredients to prove strong inapproximability results. Unfortunately, Raz's proof was very complicated. In these two talks, I will present the simplified version of his proof in detail, and survey some of the subsequent results in this area.
Date & Time
April 07, 2009 | 10:30am – 12:30pm
Location
S-101Speakers
Thomas Holenstein
Affiliation
Princeton University