Jan 14 Henry Yuen. "Anchoring games for parallel repetition" (Part 1)





The interactive transcript could not be loaded.


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.


Slides: http://arxiv.org/abs/1509.07466


When autoplay is enabled, a suggested video will automatically play next.

Up next

to add this to Watch Later

Add to

Loading playlists...