Tata Institute of Fundamental Research
Small Value Parallel Repetition for General Games
Seminar
Speaker:
Ankit Garg (Princeton University
Department of Computer Science
35, Olden Street
Princeton, NJ 08544
United States of America)
Organiser:
Jaikumar Radhakrishnan
Date:
Thursday, 21 Aug 2014, 16:00 to 17:00
Venue:
D-405 (D-Block Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: 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. We use information theoretic techniques in our proof. 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. We also extend the example of Feige and Verbitsky to show that the small-value parallel repetition bound we obtain is tight. Our techniques are elementary in that we only need to employ basic information theory and discrete probability in the small-value parallel repetition proof (this is joint work with Mark Braverman).
| Speaker: | Ankit Garg (Princeton University Department of Computer Science 35, Olden Street Princeton, NJ 08544 United States of America) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Thursday, 21 Aug 2014, 16:00 to 17:00 |
| Venue: | D-405 (D-Block Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: 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. We use information theoretic techniques in our proof. 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. We also extend the example of Feige and Verbitsky to show that the small-value parallel repetition bound we obtain is tight. Our techniques are elementary in that we only need to employ basic information theory and discrete probability in the small-value parallel repetition proof (this is joint work with Mark Braverman).