Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MULTIPROVER GAMES:
Reports tagged with multiprover games:
TR16-160 | 26th October 2016
Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

#### Multiplayer parallel repetition for expander games

Revisions: 1

We investigate the value of parallel repetition of one-round games with any number of players $k\ge 2$. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially ... more >>>

TR22-043 | 2nd April 2022
Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan

#### Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs

We prove that for every 3-player (3-prover) game $\mathcal G$ with value less than one, whose query distribution has the support $\mathcal S = \{(1,0,0), (0,1,0), (0,0,1)\}$ of hamming weight one vectors, the value of the $n$-fold parallel repetition $\mathcal G^{\otimes n}$ decays polynomially fast to zero; that is, there ... more >>>

ISSN 1433-8092 | Imprint