Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

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

Speaker: Henry Yuen (MIT)
Title: Parallel repetition for entangled games via fast quantum search
Date: Thursday 4 June 4 2015
Time: 16:00-17:00
Location: CWI room L017, Science Park 123, Amsterdam

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 ()

Please note that this newsitem has been archived, and may contain outdated information or links.