All reports by Author Ricky Rosen:

__
TR10-142
| 18th September 2010
__

Ran Raz, Ricky Rosen#### A Strong Parallel Repetition Theorem for Projection Games on Expanders

Ran Raz, Ricky Rosen

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 ...
more >>>