Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-121 | 20th June 2018 17:39

Characterizing Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy Theorem


Authors: Justin Holmgren, Lisa Yang
Publication: 25th June 2018 17:08
Downloads: 962


Non-signaling games are an important object of study in the theory of computation, for their role both in quantum information and in (classical) cryptography. In this work, we study the behavior of these games under parallel repetition.

We show that, unlike the situation both for classical games and for two-player non-signaling games, there are $k$-player non-signaling games (for $k \ge 3$) 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 is either 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 \ge 1$), and show that its non-signaling value remains exactly $(2/3)^k$ under any number of parallel repetitions.

Note: This is a continuation of a previously posted report (https://eccc.weizmann.ac.il/report/2017/178) containing significantly more general results. Section 6.1 of this report is contained nearly verbatim in the previous report.

ISSN 1433-8092 | Imprint