A Caltech Library Service

Anchoring games for parallel repetition

Bavarian, Mohammad and Vidick, Thomas and Yuen, Henry (2015) Anchoring games for parallel repetition. . (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 Paper ItemJournal Article
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.
Funding AgencyGrant Number
Simons Foundation360893
Record Number:CaltechAUTHORS:20160318-152740730
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:65490
Deposited By: Tony Diaz
Deposited On:18 Mar 2016 22:53
Last Modified:12 Oct 2022 14:20

Repository Staff Only: item control page