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.

25 February 2014, Theoretical Computer Science Seminar, Giannicola Scarpa

Speaker: Giannicola Scarpa
Title: Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost
Date: Tuesday 25 February 2014
Time: 16:00-17:00
Location: CWI Room L017, Science Park 123, Amsterdam

Abstract:

In a two-player game, two cooperating but non-communicating players, Alice and Bob, receive inputs taken from a probability distribution. Each of them produces an output and they win the game if they satisfy some predicate on their inputs/outputs. The entangled value ω*(G) of a game G is the maximum probability that Alice and Bob can win the game if they are allowed to share an entangled state prior to receiving their inputs. The n-fold parallel repetition G^n of G consists of n instances of G where Alice and Bob receive all the inputs at the same time and must produce all the outputs at the same time. They win G^n if they win each instance of G. Here we show that for any game G such that ω*(G) = 1−ε < 1, ω*(G^n) decreases exponentially in n. To prove this parallel repetition, we introduce the concept of Superposed Information Cost for entangled games which is inspired by the information cost used in communication complexity.

Joint work with Andre Chailloux

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