Parallel repetition

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 $\varphi$ , let $\mathsf{sat}(\varphi)$ denote the maximum fraction of clauses in $\varphi$ which are simultaneously satisfiable. For instance, $\varphi$ is satisfiable if and only if $\mathsf{sat}(\varphi)=1$ . One equivalent formulation of the PCP Theorem is that the following problem is NP-complete:

Formulation 1.

Given a 3-CNF formula $\varphi$ , answer YES if $\mathsf{sat}(\varphi)=1$ and NO if $\mathsf{sat}(\varphi) \leq 0.9$ (any answer is acceptable if neither condition holds).

We can restate this result in the language of 2-prover games. A 2-prover game $\mathcal G$ consists of four finite sets $Q,Q',A,A'$ , where $Q$ and $Q'$ are sets of questions, while $A$ and $A'$ are sets of answers to the questions in $Q$ and $Q'$ , respectively. There is also a verifier $V : Q \times Q' \times A \times A' \to \{0,1\}$ which checks the validity of answers. For a pair of questions $(q,q')$ and answers $(a,a')$ , the verifier is satisfied if and only if $V(q,q',a,a')=1$ . The final component of $\mathcal G$ is a probability distribution $\mu$ on $Q \times Q'$ .

Now a strategy for the game consists of two provers $P : Q \to A$ and $P' : Q' \to A'$ who map questions to answers. The score of the two provers $(P,P')$ is precisely

$\displaystyle\mathsf{val}_{P,P'}(\mathcal G) = \Pr \left[V(q, q', P(q), P(q'))=1\vphantom{\bigoplus}\right],$

where $(q,q')$ is drawn from $\mu$ . 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

$\displaystyle\mathsf{val}(\mathcal G) = \max_{P,P'} \mathsf{val}_{P,P'}(\mathcal G),$

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 $\mathcal G$ with $|A|,|A'|=O(1)$ , answer YES if $\mathsf{val}(\mathcal G)=1$ and answer NO if $\mathsf{val}(\mathcal G) \leq 0.99$ .

To see that Formulation 1 implies Formulation 2, consider, for any 3-CNF formula $\varphi$ , the game $\mathcal G_{\varphi}$ defined as follows. $Q$ is the set of clauses in $\varphi$ , $Q'$ is the set of variables in $\varphi$ , while $A = \{ TTT, TTF, TFT, FTT, TFF, FTF, FFT, FFF \}$ and $A' = \{T, F\}$ . Here $A$ represents the set of eight possible truth assignments to a three-variable clause, and $A'$ represents the set of possible truth assignments to a variable.

The distribution $\mu$ is defined as follows: Choose first a uniformly random clause $C \in Q$ , and then uniformly at random one of the three variables $x \in Q'$ which appears in $C$ . An answer $(a_C, a_x) \in A \times A'$ is valid if the assignment $a_C$ makes $C$ true, and if $a_x$ and $a_C$ are consistent in the sense that they give the same truth value to the variable $x$ . The following statement is an easy exercise:

For every 3-CNF formula $\varphi$ , we have $\mathsf{val}(\mathcal G_{\varphi}) = \frac23 + \frac13 \mathsf{sat}(\varphi)$ .

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

This completes our argument that Formulation 1 implies Formulation 2.

Parallel repetition
A very natural question is whether the constant $0.9$ in Formulation 2 can be replaced by $0.001$ (or an arbitrarily small constant). A natural way of gap amplification is by “parallel repetition” of a given game. Starting with a game $\mathcal G = \langle Q,Q',A,A',V,\mu \rangle$ , we can consider the game $\mathcal G^{\otimes k} = \langle Q^k, Q'^k, A^k, A'^k, V^{\otimes k}, \mu^{\otimes k} \rangle$ , where $\mu^{\otimes k}$ is just the product distribution on $(Q \times Q')^k \cong Q^k \times Q'^k$ . Here, we choose $k$ pairs of questions $(q_1, q'_1), \ldots, (q_k, q'_k)$ i.i.d. from $\mu$ and the two provers then respond with answers $(a_1, \ldots, a_k) \in A^k$ and $(a'_1, \ldots, a'_k) \in A'^k$ . The verifier $V^{\otimes k}$ is satisfied if and only if $V(q_i, q'_i, a_i, a'_i)=1$ for every $i = 1, 2, \ldots, k$ .

Clearly $\mathsf{val}(\mathcal G^{\otimes k}) \geq \mathsf{val}(G)^k$ because given a strategy $(P,P')$ for $\mathcal G$ , we can play the same strategy in every coordinate, and then our probability to win is just the probability that we simultaneously win $k$ independent games. But is there a more clever strategy that can do better? Famously, early papers in this arena assumed it was obvious that $\mathsf{val}(\mathcal G^{\otimes k}) = \mathsf{val}(\mathcal G)^k$ .

In fact, there are easy examples of games $\mathcal G$ where $\mathsf{val}(\mathcal G^{\otimes 2}) = \mathsf{val}(\mathcal G) = \frac12$ . (Exercise: Show that this is true for the following game devised by Uri Feige. The verifier chooses two independent random bits $b, b' \in \{0,1\}$ , and sends $b$ to $P$ and $b'$ to $P'$ . The answers of the two provers are from the set $\{1,2\} \times \{0,1\}$ . The verifier accepts if both provers answer $(1,b)$ or both provers answer $(2,b')$ .)

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 $\mathcal G$ , there exists a constant $c = O(\log(|A|+|A'|))$ such that if $\mathsf{val}(\mathcal G) \leq 1-\epsilon$ , then for every $k \in \mathbb N$ ,

$\displaystyle\mathsf{val}(\mathcal G^{\otimes k}) \leq (1-\epsilon^{3})^{k/c}.$

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

Continue reading →

Yesterday, Anup Rao pointed me to these two remarkably beautiful papers, which made my morning coffee taste a little better, and the Boston sun feel a bit warmer. I thought I’d pass on the good vibes.

Economical toric spines via Cheeger’s inequality

and

Rounding parallel repetitions of unique games

both of which have their genesis in a recent paper of Ran Raz.

I will actually post detailed notes on these developments in the coming months, as part of my upcoming course on Analytical and geometric methods in the theory of computation (and this link will also work at some point).

[Two more comments worth mentioning: First, the rounding paper above essentially matches the CMM algorithm even for non-repeated unique games, with a (perhaps) more natural algorithm. Secondly, as part of RANDOM-APPROX’08, Anup is giving a survey talk on these topics tomorrow morning (Wed, 8/27) at 9am in the Stata center.]

tcs math

some mathematics & computation

Parallel repetition

Lecture 1: Cheating with foams

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

Continue reading →

Parallel repetition, unique games, and spectral partitioning