On the Parallel Repetition Theorem

COMPUTER SCIENCE/DISCRETE MATH II
Topic:On the Parallel Repetition Theorem
Speaker:Thomas Holenstein
Affiliation:Princeton University
Date:Tuesday, April 7
Time/Room:10:30am - 12:30pm/S-101

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.