Small value parallel repetition for general games

Computer Science/Discrete Mathematics Seminar II
Topic:Small value parallel repetition for general games
Speaker:Ankit Garg
Affiliation:Princeton University
Date:Tuesday, January 20
Time/Room:10:30am - 12:30pm/S-101
Video Link:http://video.ias.edu/csdm/2015/0120-AnkitGarg

We prove a parallel repetition theorem for general games with value tending to 0. Previously Dinur and Steurer proved such a theorem for the special case of projection games. Our proofs also extend to the high value regime (value close to 1) and provide alternate proofs for the parallel repetition theorems of Holenstein and Rao for general and projection games respectively. Our techniques are elementary in that we only need to employ basic information theory and discrete probability in the small-value parallel repetition proof. I plan to cover most of the details of the proof. No prior background will be assumed. This is joint work with Mark Braverman.