@inproceedings{56fe79bb3bfe43ff9194decdf3977b68,

title = "Small value parallel repetition for general games",

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 Ver-bitsky 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.",

keywords = "Hardness amplification, Information theory, Parallel repetition",

author = "Mark Braverman and Ankit Garg",

note = "Copyright: Copyright 2016 Elsevier B.V., All rights reserved.; 47th Annual ACM Symposium on Theory of Computing, STOC 2015 ; Conference date: 14-06-2015 Through 17-06-2015",

year = "2015",

month = jun,

day = "14",

doi = "10.1145/2746539.2746565",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "335--340",

booktitle = "STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing",

}