Cryptology ePrint Archive: Report 2017/1138

(A Counterexample to) Parallel Repetition for Non-Signaling Multi-Player Games

Justin Holmgren and Lisa Yang

Abstract: We give a three-player game whose non-signaling value is constant (2/3) under any number of parallel repetitions. This is the first known setting where parallel repetition completely fails to reduce the maximum winning probability of computationally unbounded players. We also show that the best known results on non-signaling parallel repetition apply to a relatively limited class of games. In particular, these games cannot yield log-prover MIPs for languages beyond PSPACE.

Category / Keywords: foundations / parallel repetition, non-signaling strategies

Date: received 24 Nov 2017

Contact author: justin holmgren at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20171127:132508 (All versions of this report)

Short URL: ia.cr/2017/1138

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]