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.