Theory of Computing
-------------------
Title     : Parallel Repetition: Simplification and the No-Signaling Case
Authors   : Thomas Holenstein
Volume    : 5
Number    : 8
Pages     : 141-172
URL       : https://theoryofcomputing.org/articles/v005a008

Abstract
--------

Consider a game where a referee chooses (x,y) according to a publicly known
distribution; sends x to Alice, and y to Bob.  Without communicating 
with each other, Alice responds with a value  a  and Bob responds with a 
value  b.   Alice and Bob jointly win if a publicly known predicate
Q(x,y,a,b) is satisfied.

Assume that the maximum probability that Alice and Bob can win in
such a game is  v  < 1.  Raz (SIAM J. Comput. 27, 1998) shows that if
the game is repeated  n  times in parallel, then the probability
that Alice and Bob win  all  games simultaneously is at most  
(v')^{n/log(s))  where  s  is the maximal number of possible responses 
from Alice and Bob in the initial game, and  v'  is a constant depending 
only on  v.
 
In this work, we simplify Raz's proof in various ways and thus
shorten it significantly.  Further we study the case where Alice and
Bob are not restricted to local computations and can use any
strategy which does not imply communication between them.