**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 gets question , player gets question , chosen from some publicly known distribution. Players answer using deterministic functions and . They do not communicate, they win if . where the predicate is publicly known. Both want to maximize the expected value

Example 1Player A gets , Player B gets independently uniformly. Both must give answers in . They win if or .

Value equals . Indeed, can answer and pick at random in . (This is a randomized strategy. The answers provided by the provers and 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 2Projection games: given , such that .

Unique games: true also symmetricly: given , such that .

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

, since players can use the same strategy times.

**Question**: is ? Answer is NO (Lance Fortnow). Use the example above played twice. The value of is equal to . Indeed, players can arrange to win both rounds or to loose both rounds simultaneously, with equal probabilities: they play . They win iff .

**2. Results **

Ran Raz’ *parallel repetition theorem* says that for any game such that , decays exponentially, although not as fast as .

Theorem 2For any game of value , there is a constant such that

where is the length of answers in .

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 is always , like in the above examples.

**Question**: What happens if the values is close to ? I.e. writing , which can be achieved ?

The original 1995 theorem gives . In 2007, Anup Rao improved this to for projection games. This is sharp. Indeed, I found examples of games (including projection games) where .

**Question**: Can one prove , 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 for general games over expanders, and for projection games over expanders.

**3. Applications **

- Hardness of approximation.
- Geometry.
- 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 and .

Using Parallel Repetition, a stronger statement follows.

Theorem 3, such that given a projection game of size , it is NP-hard to distinguish between and .

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

UGC states that

*, such that given a unique game of size , it is NP-hard to distinguish between and .*

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.

- Show that it is NP-hard to distinguish between and , with .
- 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 , 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 , following Feige Kindler O’Donnell, Alon-Klartag,

Definition 4Acubical foamis a tiling of by -translates of a fixed tile.

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

Obvious upper bound: (cubes).

Obvious lower bound: (isoperimetric inequality).

KORW 2008: the answer is .

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

Definition 5Theodd cycle gameis as follows: Let m be odd and consider the cycle with m vertices. The first player gets a vertex from the original graph() and the second player gets either the vertex or a neighbour of the vertex(). The players reply with a color in . 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 is odd, then , since to win with probability , they should tile the circle with an odd number of tiles and alternating vertices, impossible, players must break the cycle. In fact, .

The parallel repetition is a game on a graph embedded in the -dimensional torus. Given a cubical foam, and can decide to color vertices according to the tiles they are contained in. Mistakes arise at the boundary only. So is bounded from above by the minimal area of a cubical foam.

Looking for a counterexample to Parallel Repetition, I proved that , this suggested that the solution of the foam problem should be , 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, share entangled quantum states . measures , his part of the entangled state. measures , his part of the entangled state. They get , and return , , they win iff . Thequantum valueof the game is the maximum over the all the possible shared states of the game,

The EPR paradox states that there are games for which .

Using Parallel Repetition, one can get games such that and 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 and (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 and measurements occur at time . We can make very very small and use the fact that information cannot travel faster than light (general relativity).

Thus, it should be reasonable to assume that and (Local Hidden Variable theory). Thus , but we know that this is not correct.

** References **