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.

12 August 2014, Theoretical Computer Science Seminar, Christian Schaffner

Speaker: Christian Schaffner
Title: On the Parallel Repetition of Multi-Player Games: The No-Signaling Case
Date: Tuesday 12 August 2014
Time: 16:00-17:00
Location: CWI room L017, Science Park 123, Amsterdam

Abstract

We consider the natural extension of two-player nonlocal games to an arbitrary number of players. An important question for such nonlocal games is their behavior under parallel repetition. For two-player nonlocal games, it is known that both the classical and the non-signaling value of any game converges to zero exponentially fast under parallel repetition, given that the game is non-trivial to start with (i.e., has classical/non-signaling value <1). Very recent results show similar behavior of the quantum value of a two-player game under parallel repetition. For nonlocal games with three or more players, very little is known up to present on their behavior under parallel repetition; this is true for the classical, the quantum and the non-signaling value.

In this work, we show a parallel repetition theorem for the non-signaling value of a large class of multi-player games, for an arbitrary number of players. Our result applies to all multi-player games for which all possible combinations of questions have positive probability; this class in particular includes all free games, in which the questions to the players are chosen independently. Specifically, we prove that if the original game has a non-signaling value smaller than 1, then the non-signaling value of the n-fold parallel repetition is exponentially small in n.

Joint work with Harry Buhrman and Serge Fehr
http://arxiv.org/abs/1312.7455

For more information, contact

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