Jan 14 Henry Yuen. 'Anchoring games for parallel repetition' (Part 2)

QIP 2016, Banff

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.