Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy
Speaker
Lisa Yang
Host
Akshay Degwekar, Pritish Kamath and Govind Ramnarayan
MIT CSAIL
Abstract: Non-signaling games are an important object of study in the theory of computation, both for their role in quantum information and for (classical) cryptography. In this work, we study the behavior of these games under parallel repetition.
We show that, unlike the situation both for k-player classical games (for k >= 3) and for two-player non-signaling games, there are k-player non-signaling games whose values do not tend to 0 with sufficient parallel repetition.
We show that in general:
Every game's non-signaling value under parallel repetition either is lower bounded by a positive constant or decreases exponentially with the number of repetitions.
Exponential decrease occurs if and only if the game's "sub-non-signaling value" (Lancien and Winter, CJTCS '16) is less than 1.
We also analyze a specific 3k-player game (for every k >= 1), and show that its non-signaling value remains exactly (2/3)^k under any number of parallel repetitions.
?Joint work with Justin Holmgren.?
We show that, unlike the situation both for k-player classical games (for k >= 3) and for two-player non-signaling games, there are k-player non-signaling games whose values do not tend to 0 with sufficient parallel repetition.
We show that in general:
Every game's non-signaling value under parallel repetition either is lower bounded by a positive constant or decreases exponentially with the number of repetitions.
Exponential decrease occurs if and only if the game's "sub-non-signaling value" (Lancien and Winter, CJTCS '16) is less than 1.
We also analyze a specific 3k-player game (for every k >= 1), and show that its non-signaling value remains exactly (2/3)^k under any number of parallel repetitions.
?Joint work with Justin Holmgren.?