Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-178 | 24th November 2017 09:37

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

RSS-Feed




TR17-178
Authors: Justin Holmgren, Lisa Yang
Publication: 24th November 2017 19:45
Downloads: 217
Keywords: 


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.



ISSN 1433-8092 | Imprint