4 June 4 2015, Theoretical Computer Science Seminar, Henry Yuen (MIT)

The Parallel Repetition Theorem is an important tool in complexity theory and cryptography, used to amplify the hardness of multiplayer games. It roughly states that if a game G, involving two non-communicating players, has value p, then the two-player game G^n -- n independent instances of G in parallel -- has value f(p,G)^n, where f(p,G) is some (complicated) function of p and the game. Recently, there has been much interest in proving a quantum analogue of the Parallel Repetition Theorem, where the players are allowed to use quantum entanglement as part of their strategy. We give improved parallel repetition theorems for entangled games in the case that the players' inputs are uncorrelated.

For more information, contact Ronald de Wolf (rdewolf at cwi.nl)