pdf icon
Volume 5 (2009) Article 8 pp. 141-172
Parallel Repetition: Simplification and the No-Signaling Case
Received: June 20, 2008
Published: July 29, 2009
Download article from ToC site:
[PDF (413K)]    [PS (1411K)]    [PS.GZ (327K)]
[Source ZIP]
Keywords: parallel repetition, probabilistically checkable proof
ACM Classification: F.4.1, F.1.2
AMS Classification: 68Q15, 60C05

Abstract: [Plain Text Version]

$ \newcommand{\vbar}{\bar{v}} $

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.