Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with multi-player games:
TR18-121 | 20th June 2018
Justin Holmgren, Lisa Yang

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

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 ... more >>>

TR22-167 | 23rd November 2022
Mark Braverman, Subhash Khot, Dor Minzer

Parallel Repetition for the GHZ Game: Exponential Decay

We show that the value of the $n$-fold repeated GHZ game is at most $2^{-\Omega(n)}$, improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive combinatorics.

more >>>

TR23-198 | 8th December 2023
Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer

Parallel Repetition of k-Player Projection Games

We study parallel repetition of k-player games where the constraints satisfy the projection property. We prove exponential decay in the value of a parallel repetition of projection games with value less than 1.

more >>>

ISSN 1433-8092 | Imprint