Rating is available when the video has been rented.
This feature is not available right now. Please try again later.
Published on Feb 16, 2016
QIP 2016, Banff, 10-16 January 2016
Date: Jan 14 2016 Title: "Anchoring games for parallel repetition" Authors: Mohammad Bavarian, Thomas Vidick and Henry Yuen
Two major open problems regarding the parallel repetition of multiplayer 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 these problems: we introduce a class of games we call "anchored", and then prove exponential-decay parallel repetition theorems for anchored games in the multiplayer and entangled- player settings. We then introduce a simple transformation on games called "anchoring", inspired in part by the Feige-Kilian transformation [SICOMP '00], and show that this transformation turns any (multiplayer) game into an anchored game. Together, our parallel repetition theorem and our anchoring transformation provide a simple and efficient hardness- amplification technique for general games with multiple players or with quantum players. Our anchoring transformation allows us to circumvent the need to employ the correlated sampling technique, and thus provide a way to avoid the primary obstruction to proving hardness amplification results for general games beyond the classical two-player setting.