11/07 -- parallel repetition

Two quick notes about parallel repetition:


1. In the class I hurried over the claim of the following fact: If you have a 2p1R game whose equivalent bipartite CG satisfaction problem has the projection property, then the parallel-repeated version of this game/CG-problem also has the projection property.

To see this, suppose we have a bipartite CG satisfaction problem with the projection property, so each constraint c_{(u,v)} is actually a function, pi_{(u,v)} : Sigma -> Sigma. The "k-times repeated" bipartite CG problem looks like this: Nodes on the left in the new graph correspond to all k-tuples (u_{i1}, ..., u_{ik}) where the u's are left-vertices from the old graph; nodes on the right in the new graph correspond to all k-tuples (v_{i1}, ..., v_{ik}) where the v's are right-vertices from the old-graph.

There is an edge between new vertices U := (u_{i1}, ..., u_{ik}) and V := (v_{i1}, ..., v_{ik}) precisely if there was an edge between u_{ij} and v_{ij} in the old graph for each j = 1...k. (Hence if the old graph was left-regular, so is this graph.) In the new graph, the vertices are labelled from Sigma^k. The constraint on the new edge (U,V) looks at the label (a_1, ..., a_k) for U and the label (b_1, ..., b_k) for V, and accepts iff (a_j, b_j) satisfies the old (u_{ij}, v_{ij}) constraint for each j = 1...k.

In particular, every new edge constraint has the projection property, because if I tell you a label (a_1, ..., a_k) for U, there is a unique good label for V -- namely, (pi_1(a_1), ..., pi_k(a_k)), where I have written pi_j for pi_{(u_{ij}, v_{ij})}.


2. Feige has a pretty nice survey about parallel repetition:
http://www.wisdom.weizmann.ac.il/~feige/Approx/mip.ps
It's old (from 1995), but that's okay since essentially nothing new has been proven about parallel repetition since 1995!