Tata Institute of Fundamental Research
The Parallel Repetition Theorem and Related Results
Project Seminar
Speaker:
Rakesh Venkat
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
Date:
Wednesday, 24 Nov 2010 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Rakesh Venkat School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road |
| Date: | Wednesday, 24 Nov 2010 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.