SPECIAL TIME: 11:00 -- 12:00 am,  Thursday, Dec 4, 2008

PLACE: CSE 503  

SPEAKER: Anup Rao
         Institute for Advanced Study

TITLE: Parallel Repetition: Theorems and Counterexamples


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 not so recent results
regarding this questions, covering the key ideas that have led to the
advancement of our understanding of this issue.