This the first lecture for CSE 599S: Analytical and geometric methods in the theory of computation. Today we’ll consider the gap amplification problem for 2-prover games, and see how it’s intimately related to some high-dimensional isoperimetric problems about foams. In the next lecture, we’ll use spectral techniques to find approximately optimal foams (which will then let us cheat at repeated games).

**The PCP Theorem, 2-prover games, and parallel repetition**

For a 3-CNF formula , let denote the maximum fraction of clauses in which are simultaneously satisfiable. For instance, is satisfiable if and only if . One equivalent formulation of the PCP Theorem is that the following problem is NP-complete:

Formulation 1.Given a 3-CNF formula , answer YES if and NO if (any answer is acceptable if neither condition holds).

We can restate this result in the language of 2-prover games. A 2-prover game consists of four finite sets , where and are sets of questions, while and are sets of answers to the questions in and , respectively. There is also a verifier which checks the validity of answers. For a pair of questions and answers , the verifier is satisfied if and only if . The final component of is a probability distribution on .

Now a strategy for the game consists of two provers and who map questions to answers. The score of the two provers is precisely

where is drawn from . This is just the probability that the verifier is happy with the answers provided by the two provers. The value of the game is now defined as

i.e. the best-possible score achievable by any two provers.

Now we can again restate the PCP Theorem as saying that the following problem is NP-complete:

Formulation 2.Given a 2-prover game with with , answer YES if and answer NO if .

To see that Formulation 1 implies Formulation 2, consider, for any 3-CNF formula , the game defined as follows. is the set of clauses in , is the set of variables in , while and . Here represents the set of eight possible truth assignments to a three-variable clause, and represents the set of possible truth assignments to a variable.

The distribution is defined as follows: Choose first a uniformly random clause , and then uniformly at random one of the three variables which appears in . An answer is valid if the assignment makes true, and if and are consistent in the sense that they give the same truth value to the variable . The following statement is an easy exercise:

For every 3-CNF formula , we have .

The best strategy is to choose an assignment to the variables in . plays according to , while plays according to unless he is about to answer with an assignment that doesn’t satisfy the clause . At that point, he flips one of the literals to make his assignment satisfying (in this case, the chance of catching cheating is only , the probability that is sent the variable that flipped).

This completes our argument that Formulation 1 implies Formulation 2.

**Parallel repetition**

A very natural question is whether the constant in Formulation 2 can be replaced by (or an arbitrarily small constant). A natural way of *gap amplification* is by “parallel repetition” of a given game. Starting with a game , we can consider the game , where is just the product distribution on . Here, we choose pairs of questions i.i.d. from and the two provers then respond with answers and . The verifier is satisfied if and only if for every .

Clearly because given a strategy for , we can play the same strategy in every coordinate, and then our probability to win is just the probability that we simultaneously win independent games. But is there a more clever strategy that can do better? Famously, early papers in this arena assumed it was *obvious* that .

In fact, there are easy examples of games where . (Exercise: Show that this is true for the following game devised by Uri Feige. The verifier chooses two independent random bits , and sends to and to . The answers of the two provers are from the set . The verifier accepts if both provers answer or both provers answer .)

Nevertheless, in a seminal work, Ran Raz proved the Parallel Repetition Theorem, which states that the value of the repeated game does, in fact, drop exponentially.

**Theorem 1.1: **For every 2-prover game , there exists a constant such that if , then for every ,

The exponent 3 above is actually due to an improvement of Holenstein (Raz’s original paper can be mined for an exponent of 32).