DIMACS Theoretical Computer Science Seminar


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.

See: http://paul.rutgers.edu/~yixinxu/theory-spring12.html