IQI Weekly Seminar

  Consider a one-round game G conducted between a referee and two cooperating (but noncommunicating) players: the referee asks each player a question, the players respond with answers, and the referee then determines whether the players win G or not. Such games arise in a variety of areas, from complexity theory, cryptography, and recently quantum information.     Suppose that one of two cases holds: either (a) the players have a strategy to win with probability 1, or (b) all strategies they employ have at least 1% chance of losing. Can one transform G, in a black-box way, to a one-round game H where, in case (a), the players can win with probability 1, but in case (b), the players must lose at least 99% of the time? In 1995 Raz proved that the parallel repetition of G, a new game wherein the referee plays many independent instances of G in parallel, achieves this goal. His theorem applies to games with two players that use (classical) randomized strategies.    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.    Joint work with Mohammad Bavarian and Thomas Vidick.