Computer Science/Discrete Mathematics Seminar I | |

Topic: | Analytical Approach to Parallel Repetition |

Speaker: | Irit Dinur |

Affiliation: | Weizmann Institute; Radcliffe institute |

Date: | Monday, April 15 |

Time/Room: | 11:15am - 12:15pm/S-101 |

Video Link: | https://video.ias.edu/csdm/1213/0415-IritDinur |

We propose an “analytical” framework for studying parallel repetitions of one-round two-prover games. We define a new relaxation of the value of a game, val+, and prove that it is both multiplicative and a good approximation for the true value of the game. These two properties imply Raz's parallel repetition theorem as val(G^k) ~ val+(G^k) = val+(G)^k ~ val(G)^k Using this approach, we will describe a reasonably simple proof for the NP-hardness for label-cover(1,delta), the starting point of many inapproximability results. We also discuss some new results, including * parallel repetition for small-soundness games * a new reduction from general to projection games * a tight bound for few repetitions matching Raz's counterexample. Based on joint work with David Steurer.