Skip to main content

Small Value Parallel Repetition for General Games

Author(s): Braverman, Mark; Garg, Ankit

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1mf9k
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.contributor.authorGarg, Ankit-
dc.date.accessioned2021-10-08T19:45:12Z-
dc.date.available2021-10-08T19:45:12Z-
dc.date.issued2015en_US
dc.identifier.citationBraverman, Mark, and Ankit Garg. "Small value parallel repetition for general games." In Proceedings of the forty-seventh annual ACM symposium on Theory of computing (2015): pp. 335-340. doi:10.1145/2746539.2746565en_US
dc.identifier.urihttps://eccc.weizmann.ac.il/report/2014/095/-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1mf9k-
dc.description.abstractWe 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.en_US
dc.format.extent335 - 340en_US
dc.language.isoen_USen_US
dc.relation.ispartofProceedings of the forty-seventh annual ACM symposium on Theory of computingen_US
dc.rightsAuthor's manuscripten_US
dc.titleSmall Value Parallel Repetition for General Gamesen_US
dc.typeConference Articleen_US
dc.identifier.doi10.1145/2746539.2746565-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
SmallValueParallelRepetitionGeneralGames.pdf712.74 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.