News and Events: Upcoming Events

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.