Notes of Ran Raz’ talk, jan. 19th

 

Parallel Repetition of 2 prover games

Scribes: Pierre Pansu and Sushant Sachdeva

This is a survey talk, focussed on recent results. Many of you may have heard it before.

 

1. Games

 

In a 2-player game, player {A} gets question {x}, player {B} gets question {y}, {(x,y)} chosen from some publicly known distribution. Players answer using deterministic functions {a=A(x)} and {b=B(y)}. They do not communicate, they win if {V(x,y,a,b)=1}. where the predicate {V} is publicly known. Both want to maximize the expected value

\displaystyle  \begin{array}{rcl}  Value(G)=\max_{A,\,B}\mathop{\mathbb E}_{(x,y)}(V)=\max_{A,\,B}\mathop{\mathbb P}_{(x,y)}(V(x,y,a,b)=1). \end{array}

Example 1 Player A gets {x\in\{1,2\}}, Player B gets {y\in\{3,4\}} independently uniformly. Both must give answers in {[4]}. They win if {a=b=x} or {a=b=y}.

Value equals {1/2}. Indeed, {A} can answer {a=x} and {B} pick {b} at random in {\{1,2\}}. (This is a randomized strategy. The answers provided by the provers {A(x)} and {B(y)} can depend on a common random string. It is known that even in this case, the value of the game remains the same as in the case of deterministic answers. Thus, no advantage is gained by permitting the players to use common randomness).

Example 2 Projection games: given {x,y,a}, {\exists! b} such that {V(x,y,a,b)=1}.

Unique games: true also symmetricly: given {x,y,b}, {\exists! a} such that {V(x,y,a,b)=1}.

 

Definition 1 Let {G} be a game. An {n} fold {\rm Parallel repetition} of {G} is defined as follows. {A} and {B} get {n} questions each, chosen independently following the original distribution. Both give {n} answers, depending on all {n} questions. They win iff they win at each pair {(x_i ,y_i)} of questions. Notation: {G^n}.

 

{Val(G^n)\geq Val(G)^n}, since players can use the same strategy {n} times.

Question: is {Val(G^n)= Val(G)^n} ? Answer is NO (Lance Fortnow). Use the example above played twice. The value of {G^2} is equal to {1/2=Value(G)}. Indeed, players can arrange to win both rounds or to loose both rounds simultaneously, with equal probabilities: they play {a_1 = x_1, b_1 = y_2 - 2, a_2 = x_1 + 2, b_2= y_2}. They win iff {x_1 = y_2 - 2}.

 

2. Results

 

Ran Raz’ parallel repetition theorem says that for any game {G} such that {Val(G) < 1}, {Value(G^n)} decays exponentially, although not as fast as {Val(G)^n}.

Theorem 2 For any game {G} of value {<1}, there is a constant {w<1} such that

\displaystyle  \begin{array}{rcl}  Value(G^n)\leq w^{\Omega(n/s)}, \end{array}

where {s} is the length of answers in {G}.

By a result of Feige and ??, the dependence on the length of the answers is necessary. For this talk, we can assume that the length of answers in {G} is always {1}, like in the above examples.

Question: What happens if the values is close to {1} ? I.e. writing {Value(G)=1-\epsilon}, which {w=w(\epsilon)} can be achieved ?

The original 1995 theorem gives {w=1-\epsilon^{32}}. In 2007, Anup Rao improved this to {w=1-\epsilon^{2}} for projection games. This is sharp. Indeed, I found examples of games (including projection games) where {w=1-\epsilon^{2}}.

Question: Can one prove {w=1-\epsilon}, at least for certain classes of games ?

There is an implicit bipartite graph in a 2-player game, the constraint games. With Ricky Rosen, I proved recently that {w=1-\epsilon^{2}} for general games over expanders, and {w=1-\epsilon} for projection games over expanders.

 

3. Applications

 

  1. Hardness of approximation.
  2. Geometry.
  3. Quantum information: strong EPR paradoxes.

To this list, one can add Communication Complexity (direct sum/product results), but I will not discuss this here.

 

3.1. Hardness

 

It started with Bellare-Goldreich-Sudan, Håstad.

The PCP theorem can be reformulated as followed. Given a projection game with fixed answer size, it is NP-hard to distinguish between {Value(G)=1} and {Value(G)<1-\epsilon}.

Using Parallel Repetition, a stronger statement follows.

Theorem 3 {\forall\epsilon>0}, {\exists s} such that given a projection game of size {s}, it is NP-hard to distinguish between {Value(G)=1} and {Value(G)<\epsilon}.

This is used in Håstad’s optimal hardness results for 3SAT, 3LIN, SET COVER, and later results of Feige, Khot….

UGC states that

{\forall\epsilon>0}, {\exists s} such that given a unique game of size {s}, it is NP-hard to distinguish between {Value(G)\geq 1-\epsilon} and {Value(G)<\epsilon}.

This can be used to prove a large numer of hardness results that cannot be proven from the strong PCP theorem, since you get a Unique game which is a much better starting point, e.g. [KR02], [KKMO04], [R08], etc.

Could it be proved using Parallel Repetition ? It might follow the following two steps.

  1. Show that it is NP-hard to distinguish between {Value(G)\geq 1-\alpha} and {Value(G)<1-\beta}, with {\alpha\ll\beta}.
  2. Error reduction (possibly with PR). Improve above bounds.

The problem is that this would have required a strong parallel repetition theorem, which is known to be false in general.

[ABS] seems to support this way of proving the UGC since it says it is likely that the reduction to unique games from an NP hard problem must blow up the size by {n^{poly(1/\epsilon)}}, which is the size blow-up that would be achieved in case the error reduction was performed using strong parallel repetition.

 

3.2. Geometry

 

We discuss tilings of {{\mathbb R}^n}, following Feige Kindler O’Donnell, Alon-Klartag,

Definition 4 A cubical foam is a tiling of {{\mathbb R}^n} by {{\mathbb Z}^n}-translates of a fixed tile.

 

Question: What is the minimal surface area of the tile ?

Obvious upper bound: {O(2n)} (cubes).

Obvious lower bound: {\Omega(\sqrt{n})} (isoperimetric inequality).

KORW 2008: the answer is {O(\sqrt{n})}.

This is related to parallel repetition of the odd cycle game CHTW, FKO.

Definition 5 The odd cycle game is as follows: Let m be odd and consider the cycle with m vertices. The first player gets a vertex from the original graph({x \in_R [m]}) and the second player gets either the vertex or a neighbour of the vertex({y \in_R \{x,x-1,x+1\}}). The players reply with a color in {\{0,1\}}. The players must reply with the same color if they are asked about the same vertex and with a different color if they are asked about different vertices.

If {m} is odd, then {Value(OCG)<1}, since to win with probability {1}, they should tile the circle with an odd number of tiles and alternating vertices, impossible, players must break the cycle. In fact, {Value(OCG)\leq1-\frac{1}{3m}}.

The parallel repetition {OCG^n} is a game on a graph embedded in the {n}-dimensional torus. Given a cubical foam, {A} and {B} can decide to color vertices according to the tiles they are contained in. Mistakes arise at the boundary only. So {1-Value(OCG^n)} is bounded from above by the minimal area of a cubical foam.

Looking for a counterexample to Parallel Repetition, I proved that {Value(OCG^n)\geq 1-O(\sqrt{n}/m)}, this suggested that the solution of the foam problem should be {O(\sqrt{n})}, and KORW finally found examples of foams achieving this bound.

 

3.3. Quantum information

 

Entangled two prover games have been defined by [CHTW04].

Definition 6 {A}, {B} share entangled quantum states {|s\rangle_{A,B}}. {A} measures {\hat{A}}, his part of the entangled state. {B} measures {\hat{B}}, his part of the entangled state. They get {x}, {y} and return {a=A(x,\hat{A})}, {b=B(y,\hat{B})}, they win iff {V(x,y,a,b)=1}. The quantum value of the game is the maximum over the all the possible shared states of the game,

\displaystyle  \begin{array}{rcl}  Value_Q (G)=\max_{|s\rangle_{A,B}}\max_{A,B}\mathop{\mathbb E}_{x,y}(V(x,y,a,b)). \end{array}

 

The EPR paradox states that there are games for which {Value_{Q}(G)>Value(G)}.

Using Parallel Repetition, one can get games such that {Value_{Q}(G)=1} and {Value(G)} is arbitrarily small, i.e. a reinforced Bell inequality.

Does God play dice ? Let A,B be the outcomes of the measurement. According to quantum physics, these outcomes are random from the probability distribution specified by the state.

There are some other explanations that give such outcomes without assuming randomness: (Hidden Variables theory) There exist additional variables H such that {a=a(x,y,H)} and {b=(x,y,H)} (deterministically). If the world is really deterministic, the outcome of any measurement should be known before the measurement.

Assume for simplicity that x,y are independent. A chooses x, B chooses y at time {\mathbf{t-\varepsilon}} and measurements occur at time {\mathbf{t}}. We can make {\mathbf{\varepsilon}} very very small and use the fact that information cannot travel faster than light (general relativity).

Thus, it should be reasonable to assume that {a=a(x,H)} and {b=(y,H)} (Local Hidden Variable theory). Thus {Val_Q(G) = Val(G)}, but we know that this is not correct.

 

References

 

 

Advertisements

About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See http://www.math.ens.fr/metric2011/
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s