Lecture P1. From Integrality Gaps to Dictatorship Tests

Here are Prasad Raghavendra‘s notes on one of two guest lectures he gave for CSE 599S. Prasad will be a faculty member at Georgia Tech after he finishes his postdoc at MSR New England.

In yet another excursion in to applications of discrete harmonic analysis, we will now see an application of the invariance principle, to hardness of approximation. We will complement this discussion with the proof of the invariance principle in the next lecture.

1. Invariance Principle

In its simplest form, the central limit theorem asserts the following: “As increases, the sum of independent bernoulli random variables ( random variables) has approximately the same distribution as the sum of independent normal (Gaussian with mean and variance ) random variables”

Alternatively, as increases, the value of the polynomial has approximately the same distribution whether the random variables are i.i.d Bernoulli random variables or i.i.d normal random variables. More generally, the distribution of is the approximately the same as long as the random variables are independent with mean , variance and satisfy certain mild regularity assumptions.

A phenomenon of this nature where the distribution of a function of random variables, depends solely on a small number of their moments is referred to as invariance.

A natural approach to generalize of the above stated central limit theorem, is to replace the “sum” () by other multivariate polynomials.   As we will see in the next lecture, the invariance principle indeed holds for low degree multilinear polynomials that are not influenced heavily by any single coordinate. Formally, define the influence of a coordinate on a polynomial as follows:

Definition 1 For a multilinear polynomial define the influence of the coordinate as follows:

Here denotes the variance of over random choice of .

The invariance principle for low degree polynomials was first shown by Rotar in 1979. More recently, invariance principles for low degree polynomials were shown in different settings in the work of Mossel-O’Donnell-Olekszciewicz and Chatterjee. The former of the two works also showed the Majority is Stablest conjecture, and has been influential in introducing the powerful tool of invariance to hardness of approximation.

Here we state a special case of the invariance principle tailored to the application at hand.  To this end, let us first define a rounding function as follows:

Theorem 2 (Invariance Principle [Mossel-ODonnell-Oleszkiewicz]) Let and be sets of Bernoulli and Gaussian random variables respectively. Furthermore, let

and . Let denote independent copies of the random variables and .

Let be a multilinear polynomial given by , and let . If for all , then the following statements hold:

1. For every function which is thrice differentiable with all its partial derivatives up to order bounded uniformly by ,
   

   

2. Define the function as Then, we have

2. Dictatorship Testing

A boolean function on bits is a dictator or a long code if for some . Given the truth table of a function , a dictatorship test is a randomized procedure that queries a few locations (say ) in the truth table of , and tests a predicate on the values it queried. If the queried values satisfy the predicate , the test outputs ACCEPT else it outputs REJECT. The goal of the test is to determine if is a dictator or is far from being a dictator. The main parameters of interest in a dictatorship test are :

• Completeness Every dictator function is accepted with probability at least .
• Soundness Any function which is far from every dictator is accepted with probability at most .
• Number of queries made, and the predicate used by the test.

2.1. Motivation

The motivation for the problem of dictatorship testing arises from hardness of approximation and PCP constructions. To show that an optimization problem is -hard to approximate, one constructs a reduction from a well-known -hard problem such as Label Cover to . Given an instance of the Label Cover problem, a hardness reduction produces an instance of the problem . The instance has a large optimum value if and only if has a high optimum. Dictatorship tests serve as “gadgets” that encode solutions to the Label Cover, as solutions to the problem . In fact, constructing an appropriate dictatorship test almost always translates in to a corresponding hardness result based on the Unique Games Conjecture.

Dictatorship tests or long code tests as they are also referred to, were originally conceived purely from the insight of error correcting codes. Let us suppose we are to encode a message that could take one of different values . The long code encoding of the message is a bit string of length , consisting of the truth table of the function . This encoding is maximally redundant in that any binary encoding with more than bits would contain bits that are identical for all messages. Intuitively, greater the redundancy in the encoding, the easier it is to perform the reduction.

While long code tests/dictatorship tests were originally conceived from a coding theoretic perspective, somewhat surprisingly these objects are intimately connected to semidefinite programs. This connection between semidefinite programs and dictatorship tests is the subject of today’s lecture. In particular, we will see a black-box reduction from SDP integrality gaps for Max Cut to dictatorship tests that can be used to show hardness of approximating Max Cut.

2.2. The case of Max Cut

The nature of dictatorship test needed for a hardness reduction varies with the specific problem one is trying to show is hard. To keep things concrete and simple, we will restrict our attention to the Max Cut problem.

A dictatorship test for the Max Cut problem consists of a graph on the set of vertices . By convention, the graph is a weighted graph where the edge weights form a probability distribution (sum up to ). We will write to denote an edge sampled from the graph (here ).

A cut of the graph can be thought of as a boolean function . For a boolean function , let denote the value of the cut. The value of a cut is given by

It is useful to define , for non-boolean functions that take values in the interval . To this end, we will interpret a value as a random variable that takes values. Specifically, we think of a number as the following random variable

$ latex a = -1 $ with probability and with probability  $\frac{1+a}{2}$.

With this interpretation, the natural definition of is as follows:

Indeed, the above expression is equal to the expected value of the cut obtained by randomly rounding the values of the function to as described in Equation 2.

A Dictator Cut

The dictator cuts are given by the functions for some . The of the test is the minimum value of a dictator cut, i.e.,

The soundness of the dictatorship test is the value of cuts that are far from every dictator. We will formalize the notion of being far from every dictator is formalized using influences as follows:

Cut Far From Every Dictator

Lecture 8a. A primer on simplicial complexes and collapsibility

Before we can apply more advanced fixed point theorems to the Evasiveness Conjecture, we need a little background on simplicial complexes, and everything starts with simplices.

Simplices

It’s most intuitive to start with the geometric viewpoint, in which case an -simplex is defined to be the convex hull of affinely independent points in .  These points are called the vertices of the simplex.  Here are examples for

A simplicial complex is then a collection of simplices glued together along lower-dimensional simplices.  More formally, if is a (geometric) simplex, then a face of is a subset formed by taking the convex hull of a subset of the vertices of .

Finally, a (geometric) simplicial complex is a collection of simplices such that

1. If and is a face of , then , and
2. If and , then is a face of both and .

Property (1) gives us downward closure, and property (2) specifies how simplices can be glued together (only along faces).  For instance, the first picture depicts a simplicial complex.  The second does not.

Lecture 7: The evasiveness conjecture

Continuing our look at some toplogical methods, today we’ll see the evasiveness conjecture in decision tree complexity.  In the next lecture, we’ll see how we can sometimes analyze the complexity using fixed point theorems, and their generalizations (like the Hopf index formula), following the work of Kahn, Saks, and Sturtevant.  These two lectures are co-blogged with Elisa Celis, with a lot of input from Lovasz’s lecture notes.

Decision tree complexity and evasiveness

Consider a boolean function on n bits.  We define the decision tree complexity of f as follows.  Given an unknown input , you are allowed to ask about the values of various bits of x, e.g. .  Your goal is to compute using as few questions as possible, and your questions can be adaptive, depending on answers to previous questions.  The complexity of such a strategy is the maximum number of questions asked for any .  The decision tree complexity, written , is the minimum complexity of any strategy that computes f.  (There are many other interesting models of decision complexity, see e.g. this survey.)

Clearly , because we can trivially query all the bits of x, and then output f(x).  A function f is called evasive if this upper bound is met, i.e. .  As an example, consider the parity function , where is addition modulo 2.  Clearly is evasive because after bits of x are asked about, the setting of the final bit determines the value of f.

For a more general example, consider any such that is odd.  In this case, for every , exactly one of or has the same property that the number of inputs resulting in a 1 is odd.  (These two functions are the natural restriction of f to functions on n-1 bits, which results from fixing the value of the ith bit.)  Thus an adversary could keep answering questions “?” so that the restricted function retains this property.  Since the number of inputs yielding a 1 is always odd, the restricted function always takes both possible values, implying that f is evasive–the advesary ensures that the value cannot be determined until all n possible questions are asked.

For an example of a non-evasive property, think of a point as speciying a directed graph on vertices, where there is exactly one directed edges connecting every pair of vertices, and x specifies the direction of this edge (this is called a tournament).  Thinking of the vertices as players, a directed edge from u to v means that u defeats v.  Now if the digraph specified by x has one vertex that defeats everyone else.  What is ?

Well, first we can conduct a single elimination tournament, where vertex 1 plays vertex 2, and the winner players vertex 3, and the winner of that players vertex 4, etc.  At the end, there is only one remaining vertex that remains undefeated.  Now asking more questions, we can determine whether indeeds defeats everyone else.  The total number of questions was , hence , implying that f is not evasive.

Montone graph properties and the evasiveness conjecture

Let .  In general, we can encode an arbitrary undirected N-vertex graph as an element .  A function is called a graph property if relabeling the vertices of doesn’t affect the value of .  The function f is monotone if the value of the function can never change from 1 to 0 when flipping one of the input bits from 0 to 1.  In the setting of graph properties, this corresponds to those which are maintained under addition of edges to the graph, e.g. “is G connected?” or “does G have a k-clique?”

Evasiveness Conjecture (Aanderaa-Karp-Rosenberg): Every non-trivial monotone graph property is evasive.

Here, non-trivial means that , where and denote the all-zeros and all-ones strings, respectively.

For example, consider the example “is G connected?”  The adversary is simple:  When asked about a possible edge , she answers NO unless this answer would imply that the graph is disconnected.  In other words, she answers NO unless she has answered NO already for all edges across a cut except for , in which case she has to answer YES.

Now, suppose there is a strategy which figures out the connectivity of without asking a question about some edge .  In this case, the conclusion must be that because the adversary always maintains that by answering everything in the future YES, she could force the graph to be connected.  In this case, the edges answered YES have to form a spanning tree of G (otherwise by answering all unasked questions NO, the graph would become disconnected).  Consider a path P from i to j in this YES spanning tree.  Let be the edge of P which was asked about last.  Clearly the adversary answered YES for , but this contradicts the advesary’s strategy.  Since has not been asked yet, the adversary is safe to answer NO for , and still later by answering YES on , she could force the graph to be connected.  Thus no such strategy exists, and connectivity is evasive.

Lecture 6: Borsuk-Ulam and some combinatorial applications

Now we’ll move away from spectral methods, and into a few lectures on topological methods.  Today we’ll look at the Borsuk-Ulam theorem, and see a stunning application to combinatorics, given by Lovász in the late 70’s.  A great reference for this material is Matousek’s book, from which I borrow heavily.  I’ll also discuss why the Lovász-Kneser theorem arises in theoretical CS.

The Borsuk-Ulam Theorem

We begin with a statement of the theorem.  We will think of the n-dimensional sphere as the subset of given by

Borsuk-Ulam Theorem: For every continuous mapping , there exists a point with .

Pairs of points are called antipodal.

There are a couple of common illustrative examples for the case .  The theorem says that if you take the air out of a basketball, crumple it (no tearing), and flatten it out, then there are two points directly on top of each other which were antipodal before.  Another common example states that at every point in time, there must be two points on the earth which both have exactly the same temperature and barometric pressure (assuming, of course, that these two parameters vary continuously over the surface of the eath).

The n=1 case is completely elementary.  For the rest of the lecture, let’s use and to denote the north and south poles (the dimension will be obvious from context).  To prove the n=1 case, simply trace out the path in starting at and going clockwise around .  Simultaneously, trace out the path starting at and going counter-clockwise at the same speed.  It is easy to see that eventually these two paths have to collide:  At the point of collision, .

We will give the sketch of a proof for   Let , and note that our goal is to prove that for some .  Note that is antipodal in the sense that for all .  Now, if for every , then by compactness there exists an such that for all .  Because of this, we may approximate arbitrarily well by a smooth map, and prove that the approximation has a 0.  So we will assume that itself is smooth.

Now, define by , i.e. the north/south projection map.  Let be a hollow cylinder, and let be given by so that linearly interpolates between and .

Also, let’s define an antipodality on by .  Note that is antipodal with respect to , i.e. , because both and are antipodal.  For the sake of contradiction, assume that for all .

Now let’s consider the structure of the zero set .  Certainly since , and these are h’s only zeros.  Here comes the sketchy part:  Since is smooth, is also smooth, and thus locally can be approximated by an affine mapping .  It follows that if is not empty, then it should be a subspace of dimension at least one.  By an arbitrarily small perturbation of the initial , ensuring that is sufficiently generic, we can ensure that is either empty or a subspace of dimension one.  Thus locally, should look like a two-sided curve, except at the boundaries and , where (if non-empty) would look like a one-sided curve.  But, for instance, cannot contain any Y-shaped branches.

It follows that is a union of closed cycles and paths whose endpoints must lie at the boundaries and .  ( is represented by red lines in the cylinder above.)  But since there are only two zeros on the sphere, and none on the sphere, must contain a path from to   Since is antipodal with respect to , must also satisfy this symmetry, making it impossible for the segment initiating at N to ever meet up with the segment initiating at S.  Thus we arrive at a contradiction, implying that must take the value 0.

Notice that the only important property we used about (other than its smoothness) is that is has a number of zeros which is twice an odd number.  If had, e.g. four zeros, then we could have two -symmetric paths emanating from and returning to the bottom.  But if has six zeros, then we would again reach a contradiction.

Lecture 5: Uniformizing graphs, multi-flows, and eigenvalues

In the previous lecture, we gave an upper bound on the second eigenvalue of the Laplacian of (bounded degree) planar graphs in order to analyze a simple spectral partitioning algorithm.  A natural question is whether these bounds extend to more general families of graphs.  Well-known generalizations of planar graphs are those which can be embedded on a surface of fixed genus, and, more generally, families of graphs that arise by forbidding minors.  In fact, Spielman and Teng conjectured that for any graph excluding as a minor, one should have .   Of course planar graphs have genus 0, and by Wagner’s theorem, are precisely the graphs which exclude and as minors.  In this lecture, we will follow an intrinsic approach of Biswal, myself, and Rao which, in particular, is able to resolve the conjecture of Spielman and Teng.  First, we see why even pushing the conformal approach to bounded genus graphs is difficult.

Bounded genus graphs

For graphs of bounded genus, there is hope to use an approach based on conformal mappings.  In 1980, Yang and Yau proved that

for any compact Riemannian surface of genus .  (Note that for the Laplace-Beltrami operator, one usually writes as the first non-zero eigenvalue, rather than .)  In analog with Hersch’s proof of the genus 0 case, they use Riemann-Roch to obtain a degree- conformal mapping to the Riemann sphere, then try to pull back a second eigenfunction.  A factor of the degree is lost in the Rayleigh quotient (hence the factor in the preceding bound), and Hersch’s Möbius trick is still required.

genus 0

genus 1

genus 2

genus 3

An analogous proof for graphs of bounded genus would proceed by constructing a circle packing of on the sphere , but instead of the circles having disjoint interiors, we would be assured that every point of is contained in at most circles.  Unfortunately, such a result is impossible (this has to do with the handling of branch points in the discrete setting).  Kelner has to take a different approach in his proof that for graphs of genus at most .

He starts with a circle packing of on a compact surface of genus (whose existence follows from results of Beardon and Stephenon and He and Schramm).  Then Kelner randomly subdivides repeatedly, and these subdivisions give progressively better approximations to some sequence of surfaces .  Once the approximation is of high enough quality, one applies Riemann-Roch to , and infers something about a subdivision of .  The final element is to track how the second eigenvalue of changes (in expectation) under random subdivision.

Needless to say, this approach is already quite delicate, and for graphs that can’t be equipped with some kind of conformal structure, we seem to have reached a dead end.  In this lecture, we’ll see how to use intrinsic deformations of the geometry of in order to bound its eigenvalues.  Eventually, this will reduce to the study of certain kinds of multi-commodity flows.

Metrics on graphs

Let be an arbitrary n-vertex graph with maximum degree .  Recall that we can write

where .  (Also recall that we can replace by any Hilbert space, and the same formula holds.)  The first step is to prepare this equality for “non-linearization” by getting rid of the linear condition and the sum .  (This is a popular sort of passage in the non-linear geometry of Banach spaces, which also plays a rather important role in applications to the theoretical CS.)  The goal is to get only terms that look like .  Fortunately, there is a well-known way to do this:

which follows easily from the equality when .

Thus if we want to bound , we need to find an for which the latter ratio (without the ) is .  Now, for someone who works a lot with linear programming relaxations, it’s very natural to consider a “relaxation”

where the minimization is over all pseudo-metrics d, i.e. symmetric non-negative functions which satisfy the triangle inequality, but might have even for .  Certainly , but Bourgain’s embedding theorem (which states that every n-point metric space embeds into a Hilbert space with distortion at most ) also assures us that .  Since we are trying to show that , this term is morally negligible.  One can see the paper for a more advanced embedding argument that doesn’t lose this factor, but for now we concentrate on proving that .  The embedding theorems allow us to concentrate on finding an intrinsic metric on the graph with small “Rayleigh quotient,” without having to worry about an eventual geometric representation.

As a brief preview… we are going to find a good metric by taking a certain kind of all-pairs multi-commodity flow at optimality, and weighting the edges by their congestion in the optimal flow.  Thus as the flow spreads out on the graph, it has the effect of “uniformizing” its geometry.

Discrete Riemannian metrics, convexification, and duality

Let’s now assume that is planar.  We want to show that .  First, let’s restrict ourselves to vertex weighted metrics on .  Given any non-negative weight function , we can define the length of a path in by summing the weights of vertices along it:  .  Then we can define a vertex-weighted shortest-path pseudo-metric on in the natural way

where is the set of all u-v paths in .  We also have the nice relationship

since .

So if we define

then by (1), we have .

Examples. Let’s try to exhibit weights for two well-known examples:  the grid, and the complete binary tree.

For the grid, we can simply take for all .  Clearly .  On the other hand, a random pair of points in the grid is apart, hence .  It follows that , as desired.

For the complete binary tree with root , we can simply put and for .  (Astute readers will guess the geometrically decreasing weights are actually the optimal choice.)  In this case, , while all the pairs on opposite sides of the root have .  It again follows that .  Our goal is to provide such a weight for any planar graph.

Lecture 4: Conformal mappings, circle packings, and spectral geometry

In Lecture 2, we used spectral partitioning to rule out the existence of a strong parallel repetition theorem for unique games.  In practice, spectral methods are a very successful heuristic for graph partitioning, and in the present lecture we’ll see how to analyze these partitioning algorithms for some common families of graphs.

Balanced separators, eigenvalues, and Cheeger’s inequality

Lipton and Tarjan proved that every planar graph has a negligibly small set of nodes whose remval splits the graph into two roughly equal pieces.  More specifically, every n-node planar graph can be partitioned into three disjoint sets such that there are no edges from to , the separator has at most nodes, and .  This allows one to do all sorts of things, e.g. a simple divide-and-conquer algorithm gives a linear time -approximation for the maximum independent set problem in such graphs, for any .

So there is a natural question of how well spectral methods do, for example, on planar graphs.  Spielman and Teng showed that for bounded-degree planar graphs, a simple recursive spectral algorithm recovers a partition of the vertex set so that .  In other words, for bounded-degree planar graphs, spectral methods recover the Lipton-Tarjan separator theorem!  This is proved by combining Cheeger’s inequality with their main theorem.

Theorem [Spielman-Teng]: Every n-node planar graph with maximum degree has , where is the second eigenvalue of the combinatorial Laplacian on .

Recall that we introduced the combinatorial Laplacian in Lecture 2.  If is an arbitrary finite graph, in this lecture it will make more sense to think about the Laplacian as an operator on functions given by

If we define the standard inner product , then one can easily check that for any such , we have .  In particular, this implies that is a positive semi-definite operator.  If we denote its eigenvalues by , then it is also easy to check that , with corresponding eigenfunction for every .

Thus by standard variational principles, we have

Let us also define the Cheeger constant .  For an arbitrary subset , let

,

note that this definition varies from the we defined in Lecture 2, because we will be discussing eigenfunctions without boundary conditions.  Now one defines .

Finally, we have the version of Cheeger’s inequality (proved by Alon and Milman in the discrete setting) for graphs without boundary.

Cheeger’s inequality: If is any graph with maximum degree , then

This follows fairly easy from the Dirichlet version of Cheeger’s inequality presented in Lecture 2.  Here’s a sketch:  Let satisfy , and suppose, without loss of generality, that has .  Define for and otherwise.  Then for , so we can plug into the Dirichlet version of Cheeger’s inequality with boundary conditions on .  For the full analysis, see this note which essentially follows this approach.  By examining the proof, note that one can find a subset with by a simple “sweep” algorithm:  Arrange the vertices so that , and output the best of the cuts .

So using the eigenvalue theorem of Spielman and Teng, along with Cheeger’s inequality, we can find a set with .  While this cut has the right Cheeger constant, it is not necessarily balanced (i.e. could be very small).  But one can apply this algorithm recursively, perhaps continually cutting small chunks off of the graph until a balanced cut is collected.  Refer to the Spielman-Teng paper for details.  A great open question is how one might use spectral information about to recover a balanced cut immediately, without the need for recursion.

Conformal mappings and circle packings

Now we focus on proving the bound for any planar graph .  A natural analog is to look at what happens for the Laplace-Beltrami operator for a Riemannian metric on the 2-sphere.  In fact, Hersch considered this problem almost 40 years ago and proved that , for any such Riemannian manifold .  His approach was to first use the uniformization theorem to get a conformal mapping from onto , and then try to pull-back the standard second eigenfunctions on (which are just the three coordinate projections).  Since the Dirichlet energy is conformally invariant in dimension 2, this almost works, except that the pulled-back map might not be orthogonal to the constant function.  To fix this, he has to post-process the initial conformal mapping with an appropriate Möbius transformation.

Unaware of Hersch’s work, Spielman and Teng derived eigenvalue bounds for planar graphs using the discrete analog of this approach:  Circle packings replace conformal mappings, and one still has to show the existence of an appropriate post-processing Möbius transformation.

Lecture 2: Spectral partitioning and near-optimal foams

In the last lecture, we reduced the problem of cheating in (the k-times repeated m-cycle game) to finding a small set of edges in whose removal eliminates all topologically non-trivial cycles.  Such a set is called a spine. To get some intuition about how many edges such a spine should contain, let’s instead look at a continuous variant of the problem.

Spines, Foams, and Isoperimetry

Consider again the -dimensional torus , which one can think of as with opposite sides identified.  Say that a nice set (e.g. a compact, surface) is a spine if it intersects every non-contractible loop in .  This is the continuous analog of a spine in .  We will try to find such a spine with surface area, i.e. , as small as possible.

Let’s consider some easy bounds.  First, it is clear that the set

is a spine with .  (A moment’s thought shows that this is “equivalent” to the provers playing independent games in each coordinate of .)

To get a good lower bound, it helps to relate spines to foams which tile according to , as follows.  Take two potential spines.

To determine which curve is actually a spine, we can repeatedly tile them side-by-side.

The first tiling contains the blue bi-infinite curve, which obviously gives a non-trivial cycle in , while the second yields a tiling of by bodies of volume 1.  It is easy to deduce the following claim.

Claim: A surface is a spine if and only if it induces a tiling of the plane by bodies of volume 1 which is invariant under shifts by .

By the isoperimetric inequality in , this immediately yields the bound

where is the unit -dimensional sphere.

So the the surface area of an optimal spine lies somewhere between and .  On the one hand, cubes tile very nicely but have large surface area.  On the other hand, we have sphere-like objects which have small surface area, but don’t seem (at least intuitively) to tile very well at all.  As first evidence that this isn’t quite right, note that it is known how to cover by disjoint bodies of volume at most 1 so that the surface area/volume ratio grows like .  See Lemma 3.16 in this paper, which is based on Chekuri, et. al.  It’s just that these covers are not invariant under shifts.

Before we reveal the answer, let’s see what consequences the corresponding discrete bounds would have for parallel repetition of the m-cycle game.  If the “cube bound” were tight, we would have , which doesn’t rule out a strong parallel repetition theorem ( in the previous lecture).  If the “sphere bound” were tight, we would have , which shows that .   In the latter case, the approach to proving equivalence of the UGC and MAX-CUT conjectures doesn’t even get off the ground.

As the astute reader might have guessed, recently Ran Raz proved that for some constant , showing that a strong parallel repetition theorem—even for unique games—is impossible.   Subsequently, Kindler, O’Donnell, Rao, and Wigderson showed that there exists a spine with .  While it is not difficult to show that the continuous result implies Raz’s discrete result, we will take a direct approach found recently by Alon and Klartag.

Lecture 1: Cheating with foams

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).