Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR14-095 | 8th April 2015 00:58

Small value parallel repetition for general games

RSS-Feed




Revision #1
Authors: Mark Braverman, Ankit Garg
Accepted on: 8th April 2015 00:58
Downloads: 471
Keywords: 


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.



Changes to previous version:

Fixed some typos.


Paper:

TR14-095 | 24th July 2014 21:36

Small value parallel repetition for general games





TR14-095
Authors: Mark Braverman, Ankit Garg
Publication: 24th July 2014 21:49
Downloads: 1439
Keywords: 


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.



ISSN 1433-8092 | Imprint