A k-PROVERS PARALLEL REPETITION THEOREM FOR A VERSION OF NO-SIGNALING MODEL
Ricky Rosen · Discrete Mathematics Algorithms and Applications · 2010
The parallel repetition theorem states that for any two provers one round game with value at most 1 - ∊ (for ∊ 2. We consider a special case of the No-Signaling model and show that the error of the parallel repetition of k-provers one round game, for k > 2, in this model, decreases exponentially depending only on the error of the original game and on the number of repetitions. There were no prior results for k-provers parallel repetition for k > 2 in any model.