Title: A Strong Parallel Repetition Theorem for Projection Games on Expanders
Speaker: Ricky Rosen, Princeton University
Date: Wednesday, January 18, 2012 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The parallel repetition theorem states that for any {\it 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 [Raz,Holenstein]. For {\it Projection Games}, the bound on the value of the game repeated $n$ times in parallel was improved to $(1-\lambda^2)^{\Omega(n)}$ [Rao] and this bound was shown to be tight [Raz08].
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) = {\rm 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) = {\rm poly}(\lambda)$, that is, a {\it strong parallel repetition theorem} (when $\lambda$ is constant).
This gives a strong parallel repetition theorem for a large class of two prover games.
This is a joint work with Ran Raz.