### 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