CaltechAUTHORS
  A Caltech Library Service

Anchoring games for parallel repetition

Bavarian, Mohammad and Vidick, Thomas and Yuen, Henry (2015) Anchoring games for parallel repetition. . (Submitted) http://resolver.caltech.edu/CaltechAUTHORS:20160318-152740730

[img] PDF - Submitted Version
See Usage Policy.

333Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20160318-152740730

Abstract

Two major open problems regarding the parallel repetition of games are whether an analogue of Raz's parallel-repetition theorem holds for (a) games with more than two players, and (b) games with quantum players using entanglement. We make progress on both problems: we introduce a class of games we call anchored, and prove exponential-decay parallel repetition theorems for anchored games in the multiplayer and entangled-player settings. We introduce a simple transformation on games called anchoring and show that this transformation turns any game into an anchored game. Together, our parallel repetition theorem and our anchoring transformation provide a simple and efficient hardness-amplification technique in both the classical multiplayer and quantum settings.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1509.07466arXivDiscussion Paper
ORCID:
AuthorORCID
Vidick, Thomas0000-0002-6405-365X
Additional Information:We thank Mark Braverman and Ankit Garg for useful discussions. MB was supported by NSF under CCF-0939370 and CCF-1420956. HY was supported by Simons Foundation grant #360893, and National Science Foundation Grants 1122374 and 1218547.
Funders:
Funding AgencyGrant Number
NSFCCF-0939370
NSFCCF-1420956
Simons Foundation360893
NSF1122374
NSF1218547
Record Number:CaltechAUTHORS:20160318-152740730
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20160318-152740730
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:65490
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:18 Mar 2016 22:53
Last Modified:18 Mar 2016 22:55

Repository Staff Only: item control page