Title: Parallel Repetition: Theorems and Counterexamples
Speaker: Anup Rao, Institute for Advanced Study
Date: Wednesday, September 24, 2008 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In a two player game, a referee asks two cooperating players (who are not allowed to communicate) questions sampled from some distribution and decides whether they win or not based on some predicate of the questions and their answers. The parallel repetition of the game is the game in which the referee samples $n$ independent pairs of questions and sends corresponding questions to the players simultaneously. If the players cannot win the original game with probability better than $(1-\e)$, what's the best they can do in the repeated game?
This question has connections to proving that problems are hard to approximate and to the construction of efficient "foams". In this talk, I shall survey several recent and classical results regarding this questions, covering the key ideas that have led to the advancement of our understanding of this issue.