Paper 2017/1138

The Parallel Repetition of Non-Signaling Games: Counterexamples and Dichotomy

Justin Holmgren and 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$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. STOC 2019
Keywords
parallel repetitionnon-signaling strategies
Contact author(s)
justin holmgren @ gmail com
History
2019-02-10: revised
2017-11-27: received
See all versions
Short URL
https://ia.cr/2017/1138
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1138,
      author = {Justin Holmgren and Lisa Yang},
      title = {The Parallel Repetition of Non-Signaling Games: Counterexamples and Dichotomy},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1138},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1138}},
      url = {https://eprint.iacr.org/2017/1138}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.