Published: July 29, 2009

**Keywords:**parallel repetition, probabilistically checkable proof

**Categories:**parallel repetition, probabilistically checkable proofs, PCP, complexity theory, quantum computing, cryptography

**ACM Classification:**F.4.1, F.1.2

**AMS Classification:**68Q15, 60C05

**Abstract:**
[Plain Text Version]

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 $\vbar^{\tfrac{n}{\log(s)}}$, where $s$ is the maximal number
of possible responses from Alice and Bob in the initial game, and
$\vbar<1$ 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.