Welcome to the resource topic for 2017/1138
Title:
The Parallel Repetition of Non-Signaling Games: Counterexamples and Dichotomy
Authors: Justin Holmgren, Lisa Yang
Abstract: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. In fact, parallel repetition sometimes does not decrease their value whatsoever. We show that in general: 1. 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. 2. Exponential decrease occurs if and only if the game’s sub-non-signaling value (Lancien and Winter, CJTCS '16) is less than 1.
ePrint: https://eprint.iacr.org/2017/1138
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .