TR10-142 Authors: Ran Raz, Ricky Rosen

Publication: 18th September 2010 18:49

Downloads: 1264

Keywords:

The parallel repetition theorem states that for any Two

Prover Game with value at most $1-\epsilon$ (for $\epsilon<1/2$),

the value of the game repeated $n$ times in parallel is at most

$(1-\epsilon^3)^{\Omega(n/s)}$, where $s$ is the length of the

answers of the two provers. For Projection

Games, the bound on the value of the game repeated $n$ times in

parallel was improved to $(1-\epsilon^2)^{\Omega(n)}$

and this bound was shown to be tight.

In this paper we study the case

where the underlying distribution, according to which the questions

for the two provers are

generated, is uniform over the edges of a (bipartite) expander graph.

We show that if $\lambda$ is the (normalized) spectral gap of the

underlying graph, the value of the repeated game is at most

$$(1-\epsilon^2)^{\Omega(c(\lambda) \cdot n/ s)},$$ where

$c(\lambda) = poly(\lambda)$; and if in addition the game is a

projection game, we obtain a bound of $$(1-\epsilon)^{\Omega(

c(\lambda) \cdot n)},$$ where $c(\lambda) = poly(\lambda)$, that

is, a strong parallel repetition theorem (when $\lambda$ is

constant).

This gives a strong parallel repetition theorem for a large class

of two prover games.