"Anchoring games for parallel repetition"
Thomas Vidick
(California Institute of Technology)
Monday, February 8th, 2016, 2:00 pm
EBU3B, Room 4258
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.
Based on joint work with Mohammad Bavarian (MIT) and Henry Yuen (MIT), arXiv:1509.07466.