The Parallel Repetition Theorem and Related Results

In a 2-Prover 1-Round Game, a verifier draws a pair of questions (X,Y ) from a distribution D and sends one each to two co-operating, non-communicating players who need to respond back with answers A,B. The verifier checks the answers using a known predicate V(X,Y,A,B), and declares a win or loss. The aim of the players is to plan a strategy to win the game with the highest probability over the set of questions. The n -fold parallel repetition of the game has the verifier drawing n pairs of , i.i.d., and sending each player an n-tuple of questions. The players have to respond with n answers each, one for each co-ordinate. The Parallel Repetition theorem proven by Raz states that the probability of winning the repeated game in all co-ordinates drops exponentially with n. The theorem was a key result used in proving various hardness of approximation results. In this talk, we give a brief overview of the implications of this theorem, and various related results.