{'fraction_non_alphanumeric': 0.05007604291065724, 'fraction_numerical': 0.0130957119964071, 'mean_word_length': 3.890042425754929, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 15, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 45, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Dinur’s Proof of the PCP Theorem

Probabilistically checkable proofs are proofs that can checked probabilistically by reading very few bits of the proof. In the early 1990’s, it was shown that proofs could be transformed into probabilistically checkable ones with only a modest increase in their size. The initial transformations, though elementary, were a little too complex. A recent work due to Irit Dinur gives a dramatically simple (and radically new) construction of probabilistically checkable proofs. This article explains the notion of a probabilistically checkable proof, presents the formal definition and then introduces the reader to Dinur’s work along with some of the context.


Introduction
As advances in mathematics continue at the current rate, editors of mathematical journals increasingly face the challenge of reviewing long, and often wrong, "proofs" of classical conjectures. Often, even when it is a good guess that a given submission is erroneous, it takes excessive amounts of effort on the editor's/reviewer's part to find a specific error one can point to. Most reviewers assume this is an inevitable consequence of the notion of verifying submissions and expect the complexity of the verification procedure to grow with the length of the submission. One of the main aims of this article is to point out that this is actually not the case: There does exist a format in which we can ask for proofs of theorems to be written. This format allows for perfectly valid proofs of correct theorems, while any purported proof of an incorrect assertion will be "evidently wrong" (in a manner to be clarified below). We refer to this format of writing proofs as Probabilistically Checkable Proofs (PCPs).
In order to formalize the notion of a probabilistically checkable proof, we start with a bare-bones (computationally simplified) view of logic. A system of logic is described by a collection of axioms which include some "atomic axioms" and some derivation rules. An assertion is a sentence which is simply a sequence of letters over the underlying alphabet. A proof of a given assertion is a sequence of sentences ending with the assertion, where each sentence is either one of the axioms or is obtained by applying the derivation rules to the previous sentences in the proof. An assertion which has a proof is a theorem. We will use the word argument to refer to a sequence of sentences (which may be offered as "proofs" of "assertions" but whose correctness has not been verified).
While systems of logic come in many flavors and allow varying degrees of power in their inference rules and the nature of intermediate sentences that they would allow, the "computational perspective" unifies all of these by using the following abstraction: It suggests that a system of logic is given by a computationally efficient algorithm called the verifier. The inputs to a verifier is a pair of sequences over some finite alphabet, an assertion T and evidence Π; the verifier accepts this pair if and only if Π forms a proof of T in its system of logic. Such verifiers certainly capture all known systems of logic. Indeed without the computational efficiency restriction, it would be impossible to capture the spirit that theorems are often hard to prove, but once their proofs are given, they are easy to verify. For our purposes, we associate the word "efficient" with the feature that the algorithm runs in time polynomial in the length of its inputs. (As an aside, we note that this distinction between the proving theorems and verifying proofs is currently a conjecture and is exactly the question examined under the label "Is P=NP?".) The notion that a verifier can perform any polynomial time computation enriches the class of theorems and proofs considerably and starts to offer highly non-trivial methods of proving theorems. (One immediate consequence is that we can assume theorems/proofs/assertions/arguments are binary sequences, and we will do so henceforth.) For instance, suppose we have an assertion A (say the Riemann Hypothesis), and say we believe that it has a proof which would fit within a 10,000 page article. The computational perspective says that given A and this bound (10,000 pages), one can efficiently compute three positive integers N, L, U with L ≤ U ≤ N such that A is true if and only if N has a divisor between L and U . The integers N , L, and U will be quite long (maybe writing them would take a million pages), yet they can be produced extremely efficiently (in less than the amount of time it would take a printer to print out all these integers, which is certainly at most a day or two). (This specific example is based on a result due to Joe Kilian, personal communication.) The theory of NP-completeness could be viewed as an enormous accumulation of many other equivalent formats for writing theorems and proofs. Depending on one's perspective, any such given format may or may not be a better format for writing theorems and proofs. What is important for us is that despite the fact that it differs radically from our mental picture of theorems/proofs, this is as valid a method as any. Every theorem has a valid proof, and this proof is only polynomially larger than the proof in any other system of logic, a notion referred to as "completeness". Conversely, no false assertion has a proof, a notion referred to as "soundness".
The ability to perform such non-trivial manipulations to formats in which theorems and proofs are presented raises the possibility that we may specify formats that allow for other features (that one does not expect from classical proofs). The notion of PCPs emerges from this study. Here we consider verifiers that vary in two senses: (1) The verifiers are probabilistic -they have access to a sequence of unbiased independent coins (i.e., random variables taking values from the set {0, 1} equiprobably); and (2) The verifiers have "oracle" access to the proof. I.e., to read any specific bit of the proof the verifier is allowed direct access to this bit and charged one "query" for this access. (This is in contrast to the classical notion of the Turing machine, where all information is stored on tapes and accessing the ith bit takes i units of time and implies access to all the first i bits of the proof.) However, we will restrict the number of random bits that the verifier has access to. We will also restrict the number of queries the verifier is allowed to make. The latter is definitely a restriction on the power of the verifier (classical verifiers accessed every bit of the proof). The former does not enhance the power of the verifier unless the verifier is allowed to err. So we will allow the verifier to err and consider the question: What is the tradeoff between the query complexity and the error incurred by the verifier? It must be stressed at this point that we require the error probability to be bounded away from 1 for every false assertion and every supporting argument. (It would not make any sense, given the motivation above, to assume some random distribution over theorems and proofs, and this is not being done.) Theoretical computer scientists started to examine this tradeoff starting in 1990 and have made some remarkable progress to date. We review this history below. (We remark that this is just a history of results; the notion of a probabilistically checkable proof itself evolved slowly over a long sequence of works [24,10,14,23,8,22,7], but we will not describe the evolution of this notion here.) Results constructing PCP verifiers typically restrict the number of random bits to be logarithmic in the size of the probabilistically checkable proof. Note that this is an absolute minimum limit, or else a verifier making few queries does not have a positive probability of accessing most of the bits of the proof. They then asked the question: How small can the PCP be (relative to the classical proof) and how many bits need to be queried? The first sequence of results [9,8,22] quickly established that the number of queries could be exponentially smaller than the length of the proof (e.g., in a proof of length n, the number of queries may be as small as say log 2 n), while getting nearly polynomial sized proofs (in fact, [8] obtained nearly linear sized PCPs.) The second short sequence [7,6] established what is now referred to as "The PCP Theorem", which showed that the number of bits queried could be reduced to an absolute constant(!) independent of the length of the theorem or the proof (given just the length of the proof), with PCPs of length just a polynomial in the classical proof. This immediately raised the question: What is this universal constant-the number of queries that suffices to verify proofs probabilistically? It turns out there is yet another tradeoff hidden here. It is always possible to reduce the number of queries to three bits if the verifier is allowed to err with probability very close to (but bounded away from) one. So to examine this question, one needs to fix the error probability. So, say we insist that arguments for incorrect assertions are accepted with probability (close to) half, while proofs of valid theorems are accepted with probability one. In such a case, the number of queries made by the verifier of [6] has been estimated at around 10 6 bits-not a dramatically small constant, though a constant all right! The third phase in the construction of PCPs [13,12] attempted to reduce this constant and culminated in yet another surprise. Håstad [26] shows that the query complexity could be essentially reduced to just three bits to get the above error probabilities. Subsequent work in this area has focused on the question of the size of the PCP relative to the size of the classical proofs and shown that these could be reduced to extremely small blow-ups. (Classical proofs of length n are converted to PCPs of length n · (log n) O(1) in the work of Dinur [19].) A somewhat orthogonal goal of research in PCPs has been to find simple reasons why proofs ought to be probabilistically checkable. Unfortunately, much of the above results did not help in this regard. The results from the first sequence achieved the effect by a relatively straightforward but striking algebraic transformation (by encoding information into values of algebraic functions over finite fields). Later results built on this style of reasoning but got even more complex (see, e.g., [35, page 12] for a look at the ingredients needed to get the PCP theorem of [26]). Recently, Dinur and Reingold [20] proposed a novel, if somewhat ambitious, iterative approach to constructing PCPs which was radically different from prior work. While the idea was appealing, the specific implementation was still hard and did not lead to a satisfactory alternative construction of PCPs. Subsequently, Dinur [19] finally made remarkable progress on this question, deriving the right ingredients to give a dramatically simple proof of the PCP theorem.
This work of Dinur is the focus of much of this article. We will try to outline her approach and provide context to the steps taken by Dinur which may provide further insight into her work (and highlight the novelty of the approach as well as the new technical ingredients developed in her work). The hope is that a reader, after reading this article, would be motivated to read the original work and, upon doing so, would appreciate the developments in her paper.
In what follows, we will start by setting up some basic notation and background in computational complexity in Section 2. We then introduce the formal definition of a PCP and a statement of the main result in Section 3. In this section we also introduce an alternate view of PCPs as forms of optimization problems. This language is useful in explaining Dinur's approach to constructing PCPs. In Section 4 we then describe Dinur's approach at a high level and contrast it with the earlier approaches. Dinur's approach repeatedly applies two transformations to a "current verifier", starting from a classical (non-probabilistic) verifier of proofs. The end result is a probabilistic verifier of proofs. In Sections 5 and 6 we describe the two transformations in greater detail, providing background on these (in particular, we describe some simpler transformations one may consider and why they don't work).

Preliminaries
We start by fixing some basic notation (and introducing some basic concepts such as strings and graphs).
In what follows R will denote the reals, Z the set of all integers, and Z + the set of positive integers. For x ∈ R, we let x denote the largest integer less than or equal to x. For x ∈ R, let log x denote the quantity log 2 x where log 2 denotes the logarithm of x to base 2.
By {0, 1} * we denote the set of all finite length binary sequences. (We refer to such sequences as strings.) For a string x ∈ {0, 1} * , let |x| denote its length. For random variable X taking on values in domain D and event E : D → {true, false}, we let Pr X [E(X)] denote the probability of the event E over the random choice of X. We often use the shorthand "f (n)" to denote the function n → f (n). (In particular, it will be common to use "n" to denote the argument of the function without explicitly specifying so.) Examples include the functions n 2 , log n, etc.
Later in this article we will need to resort to some terminology from "graph theory". Formally a graph G is given by a pair (V, E). The set V is finite, and its elements are called vertices. The set E is the set of edges. Each edge e ∈ E will be associated with two (not necessarily distinct) vertices, its head and tail, denoted by head(e) and tail(e). We say that e is of the form (u, v) if tail(e) = u and head(e) = v; we then say that e leaves u and enters v. The edge sets for our graphs will be symmetric: that is, each edge e of the form (u, v) will be paired with a unique edge of the form (v, u); this edge is called e − . If e is a self-loop, that is, for the form (u, u), then e −1 = e. If (u, v) ∈ E, then we refer to v as being adjacent to u or being a neighbor of u. The number of edges leaving u is called the degree of u and is denoted by deg(v) (a self-loop on v contributes one to the degree, not two). We say that a graph is d-regular if every vertex has degree d; thus, for a d-regular graph (V, E), we have |E| = d|V |. A walk in a graph is a sequence of edges e 1 , e 2 , . . . , e such that head(e i−1 ) = tail(e i ), for i = 2, . . . , . The distance between u and v is the length of the shortest walk v 0 , . . . , v satisfying v 0 = u and v = v.
We will also need in Section 6 a common extension of the notion of graphs named hypergraphs. As in graphs, hypergraphs are described by a collection of vertices and (hyper)edges, with the novelty that the hyperedges may form relations on more than two vertices. Formally, for a positive integer r, an r-uniform hypergraph is described by a pair (V, E) where V is a finite set and E is a set of subsets of V , with every e ∈ E being of size r.
2.1. Computational complexity: P, NP, proofs and optimization. The theory of computation is broadly concerned with the task of computing functions or solving "search" problems. A functional computational problem is described by a function f : {0, 1} * → {0, 1} * , and the goal is to compute f (x), given x. The running time of an algorithm A computing f is measured as a function of the input size and is denoted T A (n), where T A (n) is the maximum over all inputs x ∈ {0, 1} n of the running time of A on x. If there is a polynomial p(n) satisfying T A (n) ≤ p(n) for every n, then A is said to be a polynomial time algorithm. The class of all Boolean functions f : {0, 1} * → {0, 1} that are computable by polynomial time algorithms denotes the class P . Note that computing a Boolean function f is equivalent to deciding membership in the language (computer scientist's phrase for subsets of Many computational problems are not quite functional, but more about solving "search" problems. Consider for example the classical graph coloring problem where the input is a graph G = (V, E) and an integer k and the goal is to find a coloring A : V → {1, . . . , k} such that for every edge e of the form (u, v), it is the case that A(u) = A(v), if such a coloring exists. Problems such as coloring are characterized by the fact that there may be many "solutions" to the problem, and the goal is to find any one (or simply determine if a solution exists). Formally, such problems may be described by a relation R ⊆ {0, 1} * ×{0, 1} * . Given an input x ∈ {0, 1} * the goal is to find a solution y ∈ {0, 1} * such that (x, y) ∈ R. (In the case of graph coloring, the input x is the pair (G, k), and the solution y is the coloring A.) For simplicity we often focus on the (slightly) simpler problem of merely deciding whether x has a solution y (such that (x, y) ∈ R). This defines a language associated with a relation R, The class NP consists of all languages L R where R has "polynomially short solutions" (i.e., there is a polynomial q such that for every pair (x, y) ∈ R it is the case that |y| ≤ q(|x|)) and for which deciding validity of a solution (i.e., deciding whether (x, y) ∈ R) is in P. Graph coloring is a common example of a problem in NP. Other well-known ones include the traveling salesman problem, bin packing, finding large cliques in graphs, deciding satisfiability of a logical formula, etc.
In addition to being in the class NP, the above problems also share the common feature of being notoriously hard. No polynomial time algorithm is known to solve these problems to date. To explain this commonality (and to justify somewhat the common difficulty), the theory of NP-completeness was developed in the early '70s by Cook [18], Levin [30], and Karp [29]. Informally, an NP language L is said to be NP-complete if it is provably harder than every other problem in NP. One way to formalize this is to say that for every NP language L there exists a polynomial time computable transformation T such that for every x ∈ {0, 1} * x ∈ L if and only if T (x) ∈ L. It turns out that all the problems mentioned in the previous paragraph are also NP-complete. So in fact they are equivalent to each other, explaining their commonality. It is a widely held belief that P = NP, though at this point this remains a conjecture.
One particular NP-complete problem is the following: Fix a (reasonable) system of logic whose theorems and proofs are written as binary strings. Then the language SHORT PROOFS that consists of all theorems T that have proofs of length at most, say, |T | 2 is an NP-complete language. This is true since in any reasonable system of logic, it should be "easy" to verify proofs, where the informal term "easy" can be formalized by the requirement that the proof can be verified in time polynomial in its length. Part of the argument in favor of the belief that P does not equal NP stems from the language SHORT PROOFS. If P were equal to NP there would essentially be an "automated" efficient way to prove theorems, something that does not seem feasible. Indeed it was this perspective, the study of the complexity of theorem proving, that led Cook [18] to define the class NP.
On the other hand, much of the interest in NP-completeness arises from the perspective it sheds on "combinatorial optimization", the field that looks for efficient methods to solve optimization problems. Many of the above-mentioned problems, including graph coloring, bin packing, and the traveling salesman problem, are instances of optimization problems. NP-completeness thus provides a bridge between such combinatorial optimization and logic by showing that many optimization problems are as hard to solve as proving theorems. In what follows we will formally describe the notion of probabilistically checkable proofs and show how it adds to the study of optimization.

Probabilistically checkable proofs
A proof system is formalized by its "verifier", i.e., the algorithm that, given an assertion and supporting argument, verifies if the argument proves the assertion. Formally such a verifier is given by (an algorithm to compute) a function V : That V (T, Π) = 1 implies that the assertion T is a theorem with Π being a proof.
As mentioned earlier, we are going to enhance classical verifiers/algorithms by endowing them with access to random strings and oracles. We will denote random strings just like other strings. An oracle will just be a function O : Q → A where Q is a countable set and A is finite. The most common version is with Q = Z + and A = {0, 1}. Algorithms are allowed to compute various queries q 1 , . . . , q t and obtain answers O[q 1 ], . . . , O[q t ] to the queries. The number of queries made (t) is termed the query complexity of the algorithm. The output of a probabilistic oracle algorithm A on input x, random string R ∈ {0, 1} * and access to oracle O will be denoted A O (x; R). Notice that we will always be interested in the distribution of this random variable A O (x; R) when R is chosen uniformly from set {0, 1} (while x and O will be fixed). With this notation in hand we are ready to define PCP verifiers and the complexity class PCP. Definition 3.1. For functions r, q, a : Z + → Z + an (r, q, a)-restricted PCP verifier is a probabilistic oracle algorithm V that on input x ∈ {0, 1} n expects a random string R ∈ {0, 1} r(n) and queries an oracle Π : Z + → {0, 1} a(n) at most q(n) times and computes a "Boolean verdict" V Π (x; R) ∈ {0, 1}. Throughout this article we will assume that the queries of the PCP verifiers are made "non-adaptively"; i.e., the exact location of questions does not depend on the responses to other questions. The responses affect only the accept/reject predicate of the verifier.
The early results [9,8,22] could be described as showing that there exist polynomials p 1 , p 2 : Z + → Z + such that NP ⊆ PCP 1/2 [p 1 (log n), p 2 (log n), 1]. The PCP theorem, whose new proof we hope to outline later, may now be stated formally as . Finally, the state of the art result along these lines is that of Håstad [26] (see also [25]), which shows that for every > 0, NP = ∪ c∈Z + PCP 1 2 + [c log n, 3, 1]. One aspect we do not dwell on explicitly is the size of the "new proof". It is easy to convert an (r, q, a)-PCP verifier into one that runs in time 2 r(n) × 2 q(n) × 2 a(n) , whose queries are always in the range {1, . . . , 2 r(n)+q(n)+a(n) }. In other words, one can assume "w.l.o.g." that the proof is a string of size at most 2 r(n)+q(n)+a (n) . So in particular if the randomness and query complexity and answer length are bounded by O(log n), then the PCP proofs are still polynomial sized, and so we won't worry about the size explicitly.
3.1. PCPs and approximations. One of the principal weaknesses in the classical applications of the theory of NP-completeness to optimization problems was its inability to make any statements about the complexity of finding nearly optimal solutions to optimization problems. The PCP theorem provided a means to address this issue. Below we explain the issues in a little more detail in the context of graph coloring.
Consider the following optimization problem related to graph coloring. Given a graph G = (V, E) and integer k, find a coloring A : V → {1, . . . , k} that maximizes the number of "satisfied" edges, where an edge e = {u, v} is said to be satisfied if A(u) = A(v). If P = NP, then it is clear that this maximization problem cannot be solved in polynomial time (since such an algorithm could be used to determine in polynomial time if G is k-colorable, which is NP-complete). However, is it hard to compute a coloring A that is guaranteed to satisfy many edges, say at least .999M edges, where M denotes the number of edges that are satisfied by the optimal coloring? Such a coloring would be termed a .999 approximation to the coloring problem and is often a very good substitute for the "optimal" coloring. Significant research thus far has failed to yield a polynomial time .999 approximation algorithm for the coloring problem, but yet the theory of NP-completeness did not immediately rule out such an algorithm. All it rules out are algorithms that satisfy M edges, but an algorithm that satisfies M − 1 edges might still be conceivable.
To extend the theory of NP-completeness to rule out a .999 approximation to graph coloring, it would be useful to have a transformation T from some NPcomplete language L to graph k-coloring (for some fixed k) with the following properties: • If x ∈ L, then T (x) is k-colorable.
• If x ∈ L, then no k-coloring satisfies a .999 fraction of the edges of T (x). Such a transformation would then rule out a polynomial time .999 approximation algorithm for graph k-coloring, assuming P = NP (since then we could use the algorithm's output on T (x) to decide if x ∈ L or not).
The PCP theorem, it turns out, does indeed produce such transformations (and rules out an α-approximation algorithm for graph k-coloring for some α < 1, though this α may be larger than .999). We won't give such a transformation for the graph k-coloring problem, but a generalization of this problem. This generalization, which we call constraint graph coloring, turns out to be central to Dinur's proof of the PCP theorem. As in graph coloring, here also the task is to find a k-coloring of a given graph that maximizes the number of satisfied edges. However, we allow more general (more restrictive) conditions for satisfiability of edges. In fact the exact conditions are part of the input description. We present this definition formally below. Definition 3.4 (Constraint graph, coloring). Constraint Graph: A constraint graph G is a tuple V, E, Σ, C , where (V, E) is an undirected graph (we allow multiple edges and self-loops), Σ is a finite set called the alphabet of G, and C is a collection of constraints, c e : e ∈ E , where each c e is a function from Σ × Σ to {0, 1}. Coloring and Satisfaction: A coloring of G is a function A : V → Σ. We say that the coloring A satisfies an edge e = {u, v} if c e (A(u), A(v)) = 1. We say that the coloring A satisfies G if A satisfies all edges in G. If there is a coloring that satisfies G, then we say that G is satisfiable. We say that G is -far from satisfiable if every coloring leaves at least a fraction of the edges of G unsatisfied. Let unsat(G) = max{ : G is -unsatisfiable} = min A |{e : A does not satisfy e}| |E| .
We use G K to denote the set of constraint graphs with an alphabet of size K.
Remark. The constraints in the above definition are allowed to be arbitrary functions of two inputs, each taking values in the set Σ.
As with other optimization problems, we have a natural language associated with constraint graphs, where given a constraint graph we are required to determine if it is satisfiable. We will refer to this as the constraint graph coloring problem. Since the constraint graph coloring problem generalizes graph k-coloring, it is also NPcomplete. Dinur proves the following considerable strengthening of this assertion that says that the existence of an efficient algorithm that approximates unsat sufficiently closely would imply that P = NP.

Theorem 3.5 (Main Theorem).
There is a constant 0 > 0 such that for every language L in NP, there is a polynomial-time transformation T mapping input instances of L to G 16 such that We now show that the above theorem is closely related to the PCP theorem.
Proposition 3.6. The following are equivalent: (1) There is a constant 0 > 0 such that for for every language L in NP, there is a polynomial-time transformation T mapping input instances of L to G 16 such that Proof. Syntactically the proposition does not prove the equivalence between the PCP theorem (Theorem 3.3) and the Main Theorem (Theorem 3.5). But it is straightforward to see that 1] for every c ∈ Z + and so the Main Theorem does imply the PCP theorem. The other direction, showing PCP 1/2 [r, q, 1] ⊆ PCP 1− 0 [c·r, 2, 2] for some c < ∞ and 0 > 0, is also not too hard to show, and Proposition 6.2 essentially shows such a reduction. Modulo this caveat, the proposition above does show how the PCP theorem shows the inapproximability (to within a factor of 1 − 0 ) of the constraint graph coloring problem. Once one has such a hardness, one can then use transformations to show the hardness of approximating many other optimization problems. We won't do so here, but refer the reader to [5] for a collection of such results.
We now move to the task of describing Dinur's proof of the Main Theorem.

Overview of Dinur's approach
Before moving on to describing Dinur's approach to proving the PCP theorem, let us briefly describe the prior approaches. Though the prior approaches to proving the PCP theorem were typically stated in the "PCP s [r, q, a]" notation, the effective equivalence with constraint graph coloring allows us to interpret them in the latter language, and we do so here.

Previous approaches.
One of the principal issues to focus on is the "gap" in the unsatisfiability achieved by the transformation. Notice that the reduction we seek creates a gap between the unsatisfiability of the instances when x ∈ L and the unsatisfiability when x ∈ L; the former is 0, but the latter is at least some absolute constant . We refer to this quantity as the "gap" achieved by the reduction.
The previous approaches were very careful to maintain large gaps in reductions. Since it was unclear how to create a direct reduction from some NP complete language L to constraint graph K-coloring for finite K = |Σ| with a positive gap, the prior approaches essentially allowed K to grow with n = |x|. The results of Babai et al. [9,8] and Feige et al. [22] used algebraic techniques (representing information as coefficients of multivariate polynomials and encoding them by their evaluations) to get reductions from any NP-complete language L to constraint graph K(n)-coloring for K(n) ≈ 2 (log n) c for some constant c. 1 Arora and Safra [7] showed that transformations implicit in the PCP constructions could be composed in a nonobvious way to reduce the alphabet size dramatically. For instance, their technique could reduce K(n) to log(log(· · · (log n))) for any finite number of logarithms! This motivated the search for new PCPs that would compose better. Arora et al. [6] produced two such PCPs whose composition (several times) led to K(n) = O(1). In both the above cases, the composition reduced the gap by a constant factor, but this was okay since the composition was applied only a finite number of times.
Thus the previous approach could be described as constructing PCPs by "alphabet reduction", subject to "gap preservation". In contrast, Dinur's approach does quite the opposite. It starts with a reduction from the NP-complete language L to Max k-CSP-Σ which has minimal gap (producing only unsat(φ) ≥ 1/ poly(n) when x ∈ L), but where k and Σ are finite. She then applies a sequence of iterations that ensure "gap amplification" while "preserving alphabet size".

4.2.
Dinur's approach. The starting point for Dinur's transformation is the NPcompleteness of the graph 3-coloring problem, which we now state in a form suitable to us.
The overall strategy for proving Theorem 3.5 is as follows: We invoke Theorem 4.1 and obtain a transformation that takes the input instances of the given language L to constraint graphs (in fact, instances of the graph 3-coloring problem) with an inverse polynomial gap. Next, we work towards increasing this gap by repeatedly applying a specially designed transformation. Each application of this transformation at least doubles the gap while increasing the size of the graph by a constant factor. After roughly O(log n) applications (where n is the size of the input instance for L) of the transformation, we obtain the required constraint graph. The final transformation that justifies Theorem 3.5 has the form x → T ( ) (T 0 (x)), where = O(log |x|), T 0 is the transformation promised by Theorem 4.1, and T is a special gap-amplifying transformation invented by Dinur [19] which we will get to shortly.
First, we will work in this article with a slightly restricted class of constraint graph instances. These restrictions are not essential to our lemmas; however, they do simplify the proof of one of them (Lemma 4.6).

Definition 4.2 (Restricted constraint graphs
). An instance G ∈ G K is said to be restricted if K = 2 k for some integer k; the alphabet Σ = F k 2 is the vector space of k-dimensional vectors over F 2 , the finite field of two elements; and every constraint c e (A(u), A(v)) is given by a collection of degree two polynomials P 1 , . . . , P m over 2k variables from F 2 and the constraint c e is satisfied if and only if for every polynomial is a k-dimensional vector over F 2 , together their coordinates give a 2k-dimensional vector over F 2 , at which P j can be evaluated.) We useG K to denote the set of restricted constraint graphs with alphabet of size K.
We need one more definition before we can describe the properties of Dinur's transformation T .

Definition 4.3 (Linear-size transformation). Let G and G be sets of constraint graphs. A polynomial-time computable function
(3) the size of the output is bounded by a linear function of the size of the input; that is, there exist constants a, b ≥ 0 such that for all G ∈ G , |T (G)| ≤ a|G| + b.
Using this notation, we can now present the gap amplifying transformation referred to above. Dinur actually works directly with unrestricted instances. In this article we restrict ourselves to the restricted version; as we see below this is sufficient for our purposes.
We remark that the reduction above is totally novel in the PCP literature and already finds other applications (other than providing alternate proofs of the PCP theorem) in Dinur's paper (see [19,Section 7]). Later in this section, we describe the main ingredients in the proof of Lemma 4.4; the detailed proof appears in Section 5. Before we proceed to these, let us formally show that Theorem 3.5 follows immediately from Theorem 4.1 and Lemma 4.4.
Proof of Theorem 3.5. Let L be a language in NP , and let x be an input instance of L. We start by creating a transformation from L to T 0 which satisfies the property that T 0 (x) ∈G 16 and T 0 (x) is satisfiable if and only if x ∈ L. Given x ∈ {0, 1} n , the transform T 0 first produces a graph G such that G is 3-colorable if and only if x ∈ L, using the polynomial time transformation promised in Theorem 4.1. It then transforms G into an instance ofG 16 as follows: The set of vertices and edges of the constraint graph is the same as that of G, and the alphabet is {0, 1} 4 . The three colors {0, 1, 2} are encoded using the binary strings {0000, 0100, 1000}. For each edge {u, v} of G, we have the system of polynomial equations The first six equations ensure that only valid colors are used to color u and v; the last equation ensures that the colors assigned to u and v are different. This final constraint graph is the output of T 0 (x). Now, let T 1 be the (2, )-transformation promised by Lemma 4.4. Let m be the number of constraints in T 0 (x), and let = log m. Our final transformation T , then, is x → T ( ) 1 (T 0 (x)). Let us verify that T has the required properties. Let G 0 = T 0 (X), and for i = 1, 2, . . . , , let G i = T 1 (G i−1 ).
Completeness: T 0 takes inputs in L to satisfiable constraint graphs, and T 1 takes satisfiable constraint graphs to satisfiable constraint graphs. Thus, T takes inputs in L to satisfiable constraint graphs.
Since, 2 ≥ m, we conclude that unsat(T (x)) ≥ . Running time: To show that the total time required to compute T is bounded by a polynomial in |x|, we first argue that the size of each G i is bounded by a polynomial in |x|. This is clearly true for G 0 because T 0 can be computed in polynomial time. Since T 1 is a linear-size transformation, we (where the final inequality uses the fact that = log |T 0 (x)|.
The total running time is then bounded by the time taken to produce G 0 plus the time taken for the = O(log |x|) executions of the transform T 1 on inputs of size polynomial in |x|. Clearly, the total running time is bounded by a polynomial in |x|.
Thus our focus now shifts to Lemma 4.4, and we start to peek into its proof.

Proof of Lemma 4.4.
Dinur proves this lemma by combining two counteracting transformations. The first transformation amplifies the gap by increasing the alphabet size. The second transformation is now in the classical style, which reduces the gap somewhat, but more importantly reduces the alphabet size. While it is clear that both reductions are opposing in direction, the level of detail we have permitted ourselves above leaves it unclear as to what would happen if the two reductions were applied in sequence. Would this increase the gap or reduce it? Would it increase the alphabet size or reduce it (or preserve it)? Part of the insight behind Dinur's approach is the observation that both these transformations are especially powerful. The first allows us to amplify the gap by an arbitrary large factor, subject to a sufficiently large explosion in the alphabet size. The second brings the alphabet size to a fixed constant while paying a fixed price in terms of the gap. These terms are articulated in the assertions below. In other words, one can pick any factor c to amplify by, and there is a transformation that will achieve that amplification, provided the alphabet size is allowed to increase to an appropriately large constant depending only on c and independent of the size of the input graph. Lemma 4.6 (Alphabet reduction). There exists a constant 2 > 0 such that for all constants k, there is an ( 2 , 1)-transformation fromG K toG 16 .
Here we are buying a small alphabet size by paying for it in terms of a reduction in gap. It is important that this loss in gap, determined by the factor 2 above, is independent of alphabet size. We will elaborate more on this in a later section.
We devote separate sections to the proof of these two lemmas. For now, let us show how Lemma 4.4 follows from them.
Proof of Lemma 4.4. Consider the constant 2 given by Lemma 4.6 and set c = 2 2 . With this value of c, we obtain from Lemma 4.5 constants 1 , k > 0, and a (c, 1 )-transformation T 1 fromG 16 toG K . From Lemma 4.6, we obtain an ( 2 , 1)transformation fromG K toG 16 . Our final transformation fromG 16 toG 16 is G → T 2 (T 1 (G)). We claim that T is a (2, 1 2 )-transformation. Clearly, T can be computed in polynomial time. Since, for all G ∈G 16 thus, T incurs only a linear blow-up in size. Similarly, since T 1 and T 2 take satisfiable instances to satisfiable instances, so does their composition T . And finally, we have This concludes the proof of Lemma 4.4.
With this out of the way, we can turn our attention to gap amplification and alphabet reduction, and the proofs of Lemmas 4.5 and 4.6.

Gap amplification
We now move to the technical centerpiece of Dinur's proof of the PCP theorem. Before getting into the specifics of this problem, we first describe the context of the result and its proof. 5.1. Background: Error reduction in randomized computation. The problem of gap amplification in constraint graphs sits in the wider context of error reduction in the developing theory of randomized computation. Since every essentially randomized algorithm errs with some positive probability, it is natural to investigate whether, how, and at what cost this error can be reduced.
Let us examine the problem of gap amplification in constraint graphs in this context. It will be helpful to work in the framework of the PCP arising from constraint graphs as described in Proposition 3.6. What is a verifier? It is a randomized algorithm that examines the given proof Π in order to accept or reject. It errs when its computation accepts for some input not in the language. If the gap of the reduction is , then the probability that it errs is at most 1 − . So, indeed, to increase the gap, we need to reduce the error in the verifier's randomized algorithm.
The simplest way to reduce errors in randomized algorithms is by running the algorithm several times independently. For instance, consider one of the classical (randomized) algorithms to determine if an n-bit integer is a prime. The early algorithms (cf. [31]) had the property that they would always declare prime inputs to be "prime", but for any composite input they may declare it also to be "prime" with probability half. The classical algorithm would need an n-bit long random string to perform this test. Now, suppose we wish to reduce this error probability (of mistakenly classifying composite numbers as primes) to say 1/128; one needs only to run the basic algorithm seven times and declare a number to be prime only if every one of the seven iterations declared it to be prime. One of the drawbacks of this approach is that this process costs seven times the original in terms of randomness as well as running time. While the latter may be an affordable cost (especially for settings other than primality testing, where no polynomial time deterministic algorithm is known), the increasing cost of randomness may prove less affordable. (Unlike the case of processor speeds in computers, which under the empirically observed "Moore's Law" keep doubling every three years, physical generation of pure randomness does not seem to be getting easier over the years.) For gap amplification in PCPs, randomness is a precious resource. After error reduction, if we were to translate the PCP back into a constraint graph, the number of constraints in the resulting graph would be determined by the amount of randomness used by the verifier of the PCP (as we saw in the proof of Proposition 3.6). Since we want the the size of the constraint graph to increase by at most a constant factor, we can afford a constant additive increase only in the amount of randomness used, so even doubling the amount of randomness is, in general, unaffordable. Is there a more "randomness-efficient" way to reduce errors in randomized algorithms? This question has been studied extensively in the CS literature under the label of "recycling randomness" [1,17,28], and it is known that it suffices to use something like n + ck bits, for some absolute constant c, to reduce the error to 2 −k (though the cost in terms of running time remains a multiplicative factor of k). The most common technique for such "random-efficient" amplification is to repeat the randomized algorithm with related randomness. More formally, suppose A(x; R) denotes the computation of a randomized algorithm to determine some property of x (e.g., A(x) = 1 if and only if x is a prime integer). The standard amplification constructs a new algorithm "leaks" only one bit of information about R i , using independent random coins is completely inessential for this process. Indeed it is easy to establish the existence of subsets S ⊆ {{0, 1} n } k of cardinality only 2 O(n+k) such that the performance of A where R is chosen uniformly from S is almost as good as when drawn from the entire universe of cardinality 2 nk . The computational bottleneck here is to produce such a distribution/set S efficiently.
One popular approach to producing such a set efficiently uses the technique of "random walks" on "expander graphs". Here we create a graph G whose vertices are the space of random strings of A (i.e., V (G) = {0, 1} n ) with the property that each vertex of G is adjacent to a fixed number, D, of other vertices in G. For the application of recycling randomness it will be important that one can enumerate in time polynomial in n all the neighbors of any given vertex R ∈ {0, 1} n , though for the purpose of the PCP gap amplification it will suffice to be able to compute this in time 2 O(n) . The "random walk" technique to recycling randomness produces R = (R 1 , . . . , R k ) by first picking R 1 ∈ {0, 1} n uniformly at random, and then picking R 2 to be a random neighbor of R 1 , and R 3 to be a random neighbor of R 2 and so on. In other words, R is generated by taking a "random walk" on G.
To understand the randomness implications of this process, we first note that this process takes n + k log D bits of randomness. So it is efficient if D is small. On the other hand, the amplification property relates to structural properties of the graph. For instance, the reader can see that it wouldn't help if the graph had no edges or were just a collection of 2 n /(D + 1) disconnected complete graphs of size D + 1 each! Indeed for the amplification to work well, the graph needs to be extremely well connected or an "expander" as defined next.

Definition 5.1 (Expander graphs). For a graph
denote the set of edges going from S to its complement. The expansion of the set S, denoted e(S), is the quantity G is said to be an (η, d)-expander if G is d-regular and every set S with |S| ≤ |V |/2 has expansion e(S) ≥ η. We call an (η, d)-expander G positive if every vertex of G has at least d 2 self-loops. It is by now well known in the CS literature that if R if generated by a k-step random walk on an (η, d)-expander, then the error probability reduces to 2 −δk where δ is a universal constant depending only on η and d. (This result was first shown in a specific context by Ajtai et al. [1], and then noted for its general applicability in [17,28].) Furthermore, a rich collection of "explicit" (η, d)-expanders has been constructed, allowing for wide-ranging application of this insight. We will use the following. We do not provide a proof of this important theorem. Hoory, Linial and Wigderson [27] survey such constructions and also describe several applications.
These ideas immediately lead to PCPs where the time complexity and the amount of randomness used by the verifier are as we would like: to amplify some small gap by a factor of 2, we need to run the verifier's algorithm a constant number of times, using a constant number of more random bits than before. There is, however, still one, fatal, flaw in this method. The new verifier has to make more than two queries to the oracle, whereas in order to translate the PCP back to a constraint graph (e.g., using Proposition 3.6), we need the verifier to make just two queries. Are there ways to amplify the gap while at the same time maintaining the number of queries made by the verifier at two? 5.2. Background: Parallel repetition. For this section it is convenient to switch to the PCP language. Consider a PCP verifier V that on input x and random string R makes two queries, q 1 (R) and q 2 (R), to an oracle Π : Z + → Σ and accepts if the responses a = Π(q 1 (R)) and b = Π(q 2 (R)) satisfy f (R, a, b) = 1 for some fixed predicate f depending on x.
The naive amplification (corresponding to reduction A 4 described earlier) corresponds to the following verifier V : V picks two random strings R 1 , R 2 from the space of the randomness of V and issues queries q 1 (R 1 ), q 2 (R 1 ), q 1 (R 2 ), q 2 (R 2 ) to Π. If the responses are a 1 , b 2 , a 2 , b 2 , then V accepts if f (R 1 , a 1 , b 1 ) = 1 and f (R 2 , a 2 , b 2 ) = 1. The acceptance probability of the modified verifier V (maximized over Π) is the square of the acceptance probability of V (maximized over Π), which is good enough for us. However, it makes 4 queries, and this is the issue we wish to address in this section.
One natural attempt at reducing the number of queries may be to "combine" queries in some natural way. This is referred to as parallel repetition of PCPs. In the k-fold parallel repetition we consider a new verifier V ||⊗k that accesses an oracle Π ||⊗k : (Z + ) k → Σ k (with the association that the k coordinates in the domain correspond to k queries to Π, and the k coordinates in the range to the k responses of Π) and functions as follows: V ||⊗k picks k independent random strings R 1 , . . . , R k and queries Π ||⊗k with (q 1 (R 1 ), . . . , q 1 (R k )) and (q 2 (R 1 ), . . . , q 2 (R 2 )). If the responses of Π ||⊗k are (a 1 , . . . , a k ) and (b 1 , . . . , b k One may hope that the error in the k-fold parallel repetition goes down exponentially with k. However, any such hopes are dashed by the following example, which gives a choice of (Σ, f, q 1 , q 2 ) such that the error of the k-fold parallel repetition increases exponentially with k.
Example. Let V work with Σ = {0, 1} and the space of random strings R be {0, 1}. Let q i (R) = i + R and let f (0, a, b) = b and f (1, a, b The example illustrates some of the many problems with naive hopes one may have from parallel repetition. In the face of the above example, one may wonder if any amplification is possible at all in this setting. After many works exploring many aspects of this problem, Raz [33] gave a dramatic positive. He considers restricted verifiers whose "question" spaces (the image of q 1 (·) and q 2 (·)) are disjoint and shows that for such verifiers, error does reduce exponentially with the number of iterations, with the base of the exponent depending only on the acceptance probability of the original verifier and the answer size |Σ|. Furthermore, there exist reductions reducing any verifier to a restricted verifier losing only a constant factor in the gap. (The reader may try to see how one such reduction is implied by Proposition 6.2, Part 3.) When combined, these two steps allow us to amplify the gap in PCPs, but now we have lost the "linear size property".
Is it possible to try parallel repetition while recycling randomness? Given the difficulty in analyzing parallel repetition (Raz's proof, while essentially elementary, is already one of the most intricate proofs seen in the PCP setting), the task of combining it with recycling randomness appears forbidding. Remarkably enough, Dinur [19] manages to combine the two techniques and achieve the desired gap amplification, and does so with relatively simple proofs. Among other things, Dinur observes that even an example such as the above may not defeat the purpose. For the purposes of Lemma 4.5 it suffices to show that the acceptance probability goes down, provided it was very high to start with, and that in the remaining cases it remains bounded away from 1 (by, say, 2 k ). Dealing with cases where the acceptance probability is very high (e.g., greater than 1−|Σ| −k ) turns out be easier than dealing with the other cases. We now describe Dinur's gap amplification.

Dinur's gap amplifying transformation.
The required transformation T 1 will itself be a composition of three transformations, T 11 , T 12 and T 13 . The first two of these preprocess the input graph, turning it into a constant degree expander and preparing the ground for launching T 13 , which then delivers the required amplification. Both T 11 and T 12 lose something in the gap (the alphabet remains the same), but the amplification provided by the T 13 more than compensates this loss. In Section 5.1, we hinted at the need for conserving randomness while amplifying the gap and the role of constant-degree expander graphs in reducing the error in randomized algorithms. It turns out that gap amplification in constraint graphs is similarly facilitated if the underlying graph can be assumed to be a constant-degree expander, but the details now are rather more subtle.

Preprocessing.
We are now ready to describe the transformations T 11 and T 12 . The first of these, T 11 , converts an arbitrary constraint graph into a constantdegree graph, losing a fixed factor in the gap.

Lemma 5.3 (Constant-degree constraint graphs).
There are constants δ 1 , d > 0 such that for all k, there is a (δ 1 , 1)-transformation T 11 that transforms constraint graphs inG K into d-regular constraint graphs inG K .
Suppose we are given a G ∈G K but have no bound on the degrees of the vertices. Consider a vertex v of G whose degree deg(v) is large. The idea is to split this vertex into deg(v) vertices, dedicating one vertex for each edge incident on v in the original graph. The difficulty with this naive idea is that the coloring of the new graph could assign different colors to the different copies of v, thereby making the new constraint graph much easier to satisfy. The idea then is to connect the different copies of v using equality constraints so that any coloring that assigns wildly differing colors to the copies of v necessarily violates several of these constraints. We must, however, be careful that the graph stays bounded-degree even with the new equality constraints. A gadget achieving precisely this was invented by Papadimitriou and Yannakakis [32] using expander graphs.
Using this gadget, we can now prove Lemma 5.3.
Proof of Lemma 5.3. We fill in the details in the outline above. The transformation T 11 will transform the given graph G ∈G K into a graph G ∈G K . Let K = 2 k and Note that all constraints are still expressed as a system of polynomial equations of degree at most two. This describes the transformation T 11 . It remains to verify that it has the required properties.
It is straightforward to verify that if G is satisfiable, then G is satisfiable. Let us now argue that unsat(G ) ≥ δ 1 · unsat(G), for some absolute constant δ 1 > 0. Fix a coloring χ of G . The idea is that if the colors in a single cloud vary substantially, then by Lemma 5.4, a good fraction of the edges inside the cloud will reject. However, if some one color is used heavily in the clouds, then the situation is similar to the original graph, and a good fraction of the constraints between clouds (corresponding to edges derived from the original graph) will reject. To state this formally, consider the coloring χ for G obtained from χ by applying 'majority decoding' on each cloud: χ(v) is the color that χ assigns most frequently to the vertices of [v]. We call a vertex of G a minority vertex if its color is not shared by the majority (more than half) of the vertices in its cloud. By definition, a fraction unsat(G) of the edges of [c e (χ ) = 0].
Next consider the second term on the right-hand side of (1). This quantity is closely related to the number of minority vertices in G. Indeed, a random vertex v of G can be generated by first picking a random derived edge and then choosing one of its endpoints. Thus, [v is a minority vertex] ≥ 1 2 Pr

e∈E(G)
[e is incident on a minority vertex].

By Lemma 5.4, it follows that
[e is incident on a minority vertex].
Next, we need a transformation that will turn the constraint graph into an expander.
Proof. Let G ∈G K be the given d-regular constraint graph. Let H be an (η 0 , d 0 )expander (as in Theorem 5.2) with the same set of vertices as G. Let G be the union of G and H, where the edges of H are associated with the trivial constraint that is always true (formally represented by the empty system of polynomial equations). Now we add d + d 0 self-loops (with trivial constraints) to every vertex of G to obtain the final constraint graph G . Clearly, if G is satisfiable, then so is G .
Lemma 5.6. For all c, d, η > 0 there are constants , K > 0 such that there is a (c, )-transformation T 13 taking constraint graphs inG 16 that are (η, d)-positive expanders to constraint graphs inG K .
Let G ∈G 16 be an (η, d)-positive expander. Let unsat(G) = γ; that is, every assignment leaves a fraction γ of the edges unsatisfied. Viewing this in the framework of a PCP (as in Proposition 3.6), the verifier rejects every coloring with probability at least γ. The natural way to increase this rejection probability is for the verifier to examine several constraints at the same time. There are two concerns: (1) picking each constraint requires us to toss new coins, and if these are done independently, the size of the constraint graph we derive from the resulting PCP (by invoking Proposition 3.6) will not be linear in the size of the original graph; (2) this strategy requires the verifier to examine the colors assigned to several vertices, but in order to obtain a constraint graph in the end, we can allow at most two probes by the verifier. The first concern is addressed by picking the edges, not independently, but by taking a random walk on an expander graph. The length of the random walk will depend on the number of edges we want to examine and the amplification we wish to achieve. Since we need amplification only by a constant factor, walks of constant length will suffice. Now, let us address the second concern. Given that the edges we pick are going to be in the vicinity of the starting and ending vertices, we expand the alphabet of vertices so that at each vertex we now have information about the colors assigned to all vertices in its neighborhood; that is, every vertex u in the neighborhood v has an opinion about v's color. There is no guarantee, however, that these opinions are consistent. How, then, can we conclude that examining several edges in this manner is somehow related to examining these edges in the original graph? For this, we must look deeper into Dinur's proof.
Based on G, we will first describe a verifier that reads two locations from a proof and simultaneously checks the constraints for several edges of the original graph. This will amplify the gap. We will then transform this PCP into a new constraint graph with a larger alphabet, as we did in the proof of Proposition 3.6. 5.6. The PCP. Fix t ≥ 1. We describe the proof oracle and verifier below. The verifier probes this proof randomly at two locations and, based on the values read, decides to accept or reject. If the original constraint graph is satisfiable, then there exists a proof that the verifier accepts with probability 1. On the other hand, if the original constraint graph is -far from satisfiable, then the verifier rejects every proof with probability at least · Ω(t).
The proof: For each vertex v ∈ V (G), the proof now provides an assignment for all vertices that are within a distance t from v. We view the proof as a function

where A(v) denotes this (partial) assignment provided at vertex v. We use A(v)[w] to refer to the value A(v) assigns to vertex w, and think of A(v)[w]
as vertex v's opinion for the color that should be assigned to w in order to satisfy G. Thus, every vertex within distance t of w has an opinion for w; there is no guarantee, however, that these opinions agree with each other. Vertices w that don't appear within distance t of v are not explicitly assigned a value in A(v); for such vertices w, we say that A(v)[w] is null. Let A 1 and A 2 be two partial assignments, and let e be an edge of G of the form (u, v). We say that A 1 and A 2 pass the test at e if at least one of the following conditions holds: The verifier: The verifier picks two random vertices, a and b, of the graph and performs a test on the values stored there.
The random walk: The two vertices a and b are generated using a random walk, as follows: I. Let a = v 0 be a random vertex chosen uniformly from V (G). Repeat Step II until some condition for stopping is met.  · t · min , 1 t ,

Proof. Part (a) is straightforward. Given a satisfying assignment A for G, let the proof be the assignment A such that A(v)[w] = A(w).
The idea for part (b) is the following: Fix an assignment A. We will argue that for such an assignment A to succeed in convincing the verifier, the opinions of different vertices must be generally quite consistent. This suggests that a good fraction of A is consistent with a fixed underlying assignment A for G. Now, since G is -far from satisfiable, A must violate at least a fraction of the constraints in G. Since the verifier examines t edges on an average, the expected number of unsatisfied edges it encounters is t . Most of the work will go into showing that when it does encounter these edges, it rejects with a sufficient probability and that these rejections are not concentrated on just a few of its walks. In our analysis we will use the following fact, which formalizes the memoryless nature of the verifier's random walk. (We omit the proof.)

Lemma 5.8 (Fact about the random walk). Let e ∈ E(G) be of the form (u, v).
Consider the verifier's walks conditioned on the event that the edge e appears exactly k times (for some k ≥ 1) in the walk, that is, the number of i's for which e i = e (in particular, v i−1 = u and v i = v) is exactly k. Conditioned on this event, consider the starting vertex, a, and the ending vertex, b. We claim that a and b are independent random variables. Furthermore, a has the same distribution as the random vertex obtained by the following random process.
Start the random walk at u, but stop with probability 1 t before making each move (so we stop at u itself with probability 1 t ). Output the final vertex. Similarly, we claim that b can be generated using a random walk starting from v and stopping with probability 1 t before each step. Now, fix a proof A. Let us "decode" A and try to obtain an assignment A for G. The idea is to define A(u) to be the most popular opinion available in A for u, but motivated by Lemma 5.8, the popularity of an opinion will be determined by considering a random walk. The new assignment A for G: To obtain A(u), we perform a random walk starting from u mentioned in Lemma 5.8 (stopping with probability 1 t before each step). Restrict attention to those walks that stop within t − 1 steps. Let the vertex where the walk stops be b u . This generates a distribution on the vertices of G. For each letter σ in the alphabet, determine the probability (under this distribution) that b u 's opinion for u is σ. Then, let A(u) be the letter that has the highest probability. Formally, We now relate the verifier's probability of rejection to the the fraction of edges of G left unsatisfied by A. Since G is -far from satisfiable, a fraction of the edges of G is left unsatisfied by A. We wish to argue that whenever the verifier encounters one of these edges in its walk, it is likely to reject the walk. Let F be a subset of these unsatisfied edges of the largest size such that |F | ≤ 1 t . Then,  A(b) fail the test at e i . Let N be the random variable denoting the number of faulty edges on the verifier's walk.
Since the verifier rejects whenever it encounters a faulty edge on its walk, it is enough to show that N > 0 with high enough probability. We will prove the following two claims.
Let us now assume that these claims hold, and complete the proof of Lemma 5.7: For the second inequality, we used the fact (which follows from the Chebyshev-Cantelli inequality; see also Alon and Spencer [4, Section 4.8, Ex. 1]) that for any non-negative random variable X, . For the last inequality we used (4).

Proofs of the claims.
Proof of (5). We will estimate the expected number of faulty occurrences for each edge in F . Fix one such edge e of the form (u, v), and let N e denote the number of faulty occurrences of e in the verifier's walk. Let #e denote the number of occurrences (not necessarily faulty) of e in the walk. Note that the i-th edge of the walk is uniformly distributed over the set of all edges, and so E[#e] = t |E| for all e. Condition on the event #e = k, and consider the starting vertex a and the ending vertex b. By Lemma 5.8, a and b can be generated using independent lazy random walks starting at u and v respectively. The probability that the walk to generate a traverses t or more edges is 1 − 1 If A(a) and A(b) fail the test at e, then all the k occurrences of e in the walk are considered faulty. Thus, Finally, summing over all e ∈ F , we have We have shown that the expected number of faulty edges on the verifier's walk is large. However, this does not automatically imply that the number of faulty edges is positive with reasonable probability, for it could be that faulty edges appear on the verifier's walk in bursts and just a few walks account for the large expectation. This is where we use the fact that our underlying graph is an expander. Intuitively, one expects that a random walk in an expander graph is not likely to visit the small set of edges, F , too many times. The following proposition quantifies this intuition by showing that in the random walk the events of the form "e i ∈ F " are approximately pairwise independent. Proposition 5.11 (see Dinur [19]). For j > i, A proof of this proposition appears in Appendix B.
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use

ON DINUR'S PROOF OF THE PCP THEOREM 43
Proof of (6). Let χ i be the indicator random variable for the event "e i ∈ F ". Then, where we used Proposition 5.11 in (7). Claim (6) follows from this because we have assumed (see (4) above) that |F | |E| ≤ 1 t .

The final constraint graph.
It is relatively straightforward to model the PCP described above as a constraint graph. There is one technicality that we need to take care of: the verifier's walks are not bounded in length, and a naive translation would lead to a graph with infinitely many edges. We now observe that we can truncate the verifier's walk without losing much in the rejection probability.
Verifier with truncated walks: We will show that a version of Lemma 5.7 holds even when the verifier's walks are truncated at T * = 5t, and it just accepts if its walk has not stopped within these many steps.

Lemma 5.12 (Truncated verifier). Suppose the constraint graph G with alphabet
Σ is an (η, d)-expander. Consider the verifier with truncated walks.

(a) If G is satisfiable, then there is a proof that the verifier accepts with probability 1. (b) If G is -far from satisfiable, then the verifier rejects every proof with probability at least
Proof. We show only how the previous proof is to be modified in order to justify this lemma. If the verifier's walk is truncated before stopping, then no edge on the walk is declared faulty. Under this definition, let N be the number of faulty edges in the verifier's random walk (N = 0 whenever the walk is truncated). Let us redo Claim (5). Let I{T ≥ T * + 1} be the indicator random variable for the event T ≥ T * + 1. Then, N = N − N · I{T ≥ T * + 1}, and We already have a lower bound for E[N] in Claim (5), so it is sufficient to obtain an upper bound for the second term on the right, which accounts for the contribution to E[N] from long walks. The contribution to E[N] from walks of length is at most |F |/|E| times the probability that T = . So, the contribution to E[N] from walks of length at least T * + 1 is The first factor is at most (1 − 1 t ) T * ; the second is T * + t. So, Thus, from (8), we obtain Note that N ≤ N, so the upper bound in (6)  Definition 5.13 (The product constraint graph). Let G be a d-regular constraint graph with alphabet Σ. The product graph G t is defined as follows.
• The vertex set of the graph G t is V (G).
• The alphabet for G t is Σ (d+1) t .
• The edges and their constraints correspond to the verifier's actions outlined above. We imagine that the verifier's moves are described by a random string of length T * over the set [d] × [t]. The first component determines which outgoing edge the verifier takes, and it stops after that step if the the second component is 1 (say). For each vertex a and each sequence τ , we have an edge labeled τ leaving (with tail) a, corresponding to the walk starting from vertex a determined by τ . • If the walk does not terminate at the end of τ , then the ending vertex (i.e. head) of this edge is also a (it is a self-loop), and the constraint on that edge is always satisfied. • If the walk does terminate and the final vertex is b, then the edge labeled τ has the form (a, b), and its constraint is the conjunction of all constraints of G checked by the verifier along this walk. Note that in G the constraints were represented by a system of polynomial equations of degree at most two; then the constraints in G t also have the same form.
Thus, every vertex has (dt) T * edges leaving it, and the total number of edges in G t is exactly |V (G)| · (dt) T * .
Lemma 5.14. For all constants t, the function T 13 : G → G t (where G is a restricted constraint graph that is an (η, d)-positive expander) is a t depends only on the alphabet of the original graph and the parameter t. The constraints of G t are represented as a system of polynomial equations of degree at most two; thus, G t ∈G K where K = |Σ(G t )|.
Lemma 5.6 follows immediately from this.

Alphabet reduction
Recall that in this section we wish to prove Lemma 4.6, reproduced below.
For the purposes of this section it will be useful to consider a further generalization of the constraint graph coloring problems to "hypergraph constraints". This definition is motivated by the fact that the proof of Lemma 4.6 will reduce graph coloring on arbitrary alphabets to hypergraph coloring over a fixed alphabet and then convert this back to a constraint graph coloring problem.
The constraint hypergraph coloring problem is a generalization of the constraint graph coloring problem to r-uniform hypergraphs with each constraint applying to edges to the hypergraph. The following definition captures this notion formally. Definition 6.1 (Constraint hypergraph, coloring). For a positive integer r, an r-constraint hypergraph G is a tuple V, E, Σ, C , where (V, E) is an r-uniform hypergraph (we allow multiple edges and multiple incidences of the same vertex in an edge), Σ is a finite set called the alphabet of G, and C is a collection of constraints, c e : e ∈ E , where each c e is a function from Σ r → {0, 1}. A coloring of G is a function A : V → Σ. We say that the coloring A satisfies an edge e of the form (u 1 , . . . , u r ) if c e (A(u 1 ), . . . , A(u r )) = 1. We say that the coloring A satisfies G if A satisfies all edges in G. If there is a coloring that satisfies G, then we say that G is satisfiable. We say that G is -far from satisfiable if every coloring leaves at least a fraction of the edges of G unsatisfied. Let unsat(G) = max{ : G is -unsatisfiable} = min A |{e : A does not satisfy e}| |E| .
We use G (r) K to denote the set of r-constraint graphs with an alphabet of size K. When K = 2 k , Σ = F k 2 and the constraints c e are given by a system of quadratic (degree two) polynomials over the rk variables from F 2 representing the colors of the r underlying variables, we say that the constraint hypergraph is a restricted constraint hypergraph. We useG (r) K to denote the set of restricted constraint graphs. To motivate our main lemmas we start by describing some of the basic (and well-known) reductions between constraint hypergraph coloring problems. These results don't really suffice to prove Lemma 4.6, but thinking about this proposition provides a good warm-up to thinking about reductions. It also emphasizes the novelty in the lemma. (2) There exists a (1/2 r+2 , 1)-transformation fromG (3) There exists a (1/r, 1)-transformation fromG (r) License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use

JAIKUMAR RADHAKRISHNAN AND MADHU SUDAN
Proof of sketch. We won't really prove Parts 1 and 2, since they are somewhat tangential to our goal and furthermore quite elementary. But we will provide some hints before giving a somewhat more detailed sketch of the proof of Part 3. The first part is easy to achieve by simply viewing every vertex of an instanceG (r) K as k vertices from an instance ofG (rk) 2 . A 2 k -coloring can then be viewed as binary coloring of the k corresponding vertices, and constraints now apply to r · k vertices at a time. The properties of the transformation can now be verified easily. The second part follows from the classical reduction from r-SAT to 3-SAT (due to [18]). Note that this reduction can be set up to create only restricted instances.
Finally, the third part: This part is based on a result of Fortnow, Rompel and Sipser [23]. Consider an instance G ofG (r) K with vertices V , edges E, on alphabet Σ and constraints c e e∈E . The vertices of the transformed instance G will consist of a vertex u for every vertex u ∈ V and e for every edge e ∈ E. Colorings A to the vertices of G take values in the set Σ r . Let A (u ) i denote the ith coordinate of such a coloring (which lies in Σ). Corresponding to a constraint c e (u 1 , . . . , u r ) of G, the instance G will consist of r constraints c e,i , one for each i ∈ [r]. The constraint c e,i applies to the variables u i and e and is satisfied by an assignment A if and only if c e (A (e )) = 1 and A (e ) i = A (u i ) 1 . It is easy to see that the transformation preserves linear size (the number of constraints of G is r times the number of constraints of G). It can also be verified that if A is an assignment to the vertices of G satisfying every constraint of G, then any assignment satisfying A (u ) 1 = A(u) and A (e) = (A(u 1 ), . . . , A(u r )) for e = u 1 , . . . , u r satisfies every constraint of G . Finally given an assignment A to the instance G consider the assignment A(u) = A (u ) 1 for every u ∈ G. We claim that if A fails to satisfy a fraction /r of the constraints of G , then A fails to satisfy only a fraction of the constraints of G. To see this it suffices to note that if for some e ∈ E the constraints c e,i are satisfied by A for every i ∈ [r], then c e is satisfied by A since where the first equality is by the definition of A, the second by the second condition in the satisfiability of (all of) the c e,i 's, and the third equality from the first condition of the satisfiability of (any of) the c e,i 's.
The above proposition gives a rich collection of simple transformations between constraint hypergraph coloring problems. Indeed if we put together Parts 1, 2, and 3 of Proposition 6.2 above, we get a transformation fromG K toG 2 3 , which is one of the goals of Lemma 4.6. The weakness of Proposition 6.2 becomes apparent when we consider the guarantees we get from it. A straightforward application yields a (1/(3 · 2 2k+2 ), 1)-transformation fromG K toG 8 which fails the promise that the gap of the reduction would reduce by a factor independent of k. It is this aspect that makes Lemma 4.6 quite non-trivial and forces a significant departure from standard transformations of this nature. Fortunately work done in the 1990's (in particular, the work of Arora et al. [6]) gives a much stronger version which suffices for our purposes. We paraphrase their result in our language here. Lemma 6.3. There exists an 3 > 0 such that for all integers K there exists an ( 3 , 1)-transformation fromG K toG (4) Proving this lemma will occupy us for the rest of this section. But first we note that this lemma immediately yields Lemma 4.6.
Proof of Lemma 4.6. We compose the transformation from Lemma 6.3 with the one from Part 3 of Proposition 6.2. The composition yields a ( 3 /4, 1)-transformation, where 3 is the constant of Lemma 6.3, thus yielding Lemma 4.6 for 2 = 3 /4.
We now focus on the task of transformingG K toG (4) 2 . The steps in the transformation will be similar to the steps of the transformation given above in the proof of Part 1 of Proposition 6.2 (only each step will now be significantly more complex). We will start by "transforming" the vertices, explaining how to interpret colorings of one instance as colorings of the other. Then we will transform the constraints of the source instance. Analyzing this process will then yield the reduction. The following two sections (Sections 6.1 and 6.2) introduce some of the machinery. Section 6.3 presents the actual transformation which is then analyzed in Section 6.4.

Encodings of vertex colorings.
In the proof of Part 1 of Proposition 6.2, we transformed K = 2 k coloring to 2 coloring (of hypergraphs). This transformation converted a single vertex u of G ∈G A (u 1 ), . . . , A (u k ) were thus in one to one correspondence with each other, allowing us to compare colorings of G with colorings of G. While this made the analysis simple, it also introduced essential weaknesses in the transformation. In Part 1 of Proposition 6.2, this led to making the edges of the hypergraph larger by a factor of k. If we didn't want to pay such a price and keep the hyperedges small, then the reduction would have lost at least 1/k in its strength. While we won't go into details, this loss boils down to the fact that two different colorings A 1 (u) = a and A 2 (u) = a might be discernible only by considering the colors of one of the k corresponding vertices u 1 , . . . , u k . In turn this weakness boils down to the fact that in translating the K-coloring of G to a 2-coloring of G we adopted a simplistic representation of elements of K as binary strings-one which was not very good at distinguishing distinct elements of K. As we will see shortly, one can do much better by picking better, so-called "error-correcting" representations.

. The colorings A(u) and
Below we will refer to a function E : {0, 1} k → {0, 1} as an "encoding" of elements of {0, 1} k . Corresponding to an encoding function, we will also consider decoding functions D : {0, 1} → {0, 1} k . Relative to such encoding functions our transformations from G ∈G K to G ∈G (4) 2 will proceed by creating vertices u 1 , . . . , u in G for each vertex u ∈ G. (There will be additional vertices and of course some edges and constraints, corresponding to the constraints of G, but we will describe those later.) The intent will be to show that if G is satisfied by the coloring A, then G is satisfied by a coloring A which assigns to the vertex u i the color E(A(u)) i . Similarly when it comes to analyzing unsatisfiable instances we will infer properties of a coloring A to the vertices of G by considering the induced coloring A given by A(u) = D (A (u 1 ), . . . , A (u )). Motivated by this intention, we now describe the encoding and decoding function we will use and some interesting properties of this encoding function. For the decoding we will use a canonical decoding function. For strings x, y ∈ {0, 1} let δ(x, y) = |{i|x i =y i }| . We say x is δ-close to y if δ(x, y) ≤ δ.
The Hadamard decoding of a string x ∈ {0, 1} 2 k , denoted H −1 (x), is defined to be the string a which minimizes δ (H(a), x) with ties being broken arbitrarily. In what follows we will show some nice properties of the Hadamard encoding (and decoding) function.
The properties of the Hadamard encoding in turn go back to the properties of linear functions. From this point onward we will view the elements {0, 1} as elements of the field F 2 and {0, 1} k as a k dimensional vector space over F 2 . In particular for x, y ∈ {0, 1} k we will let x + y denote their vector sum in F k 2 .
. . , Z n−1 ] is a non-zero polynomial of degree at most d − d 1 . By the induction hypothesis, Pr z ∈S n−1 [p 1 (z ) = 0] ≥ d−d 1 |S| . Let h(Z n ) = p(z , Z n ). Given that p 1 (z ) = 0, h(Z n ) is a degree d 1 polynomial, and the event that p(z) = 0 is equivalent to the event that h(z n ) = 0, which happens with probability at most The properties of the Hadamard encoding that make it useful in our transformation relate to its "local correctibility" and the "local testability". Proof. The first assertion follows easily by contradiction. Suppose there exist a = b such that δ (H(a), X), δ(H(b), X) < 1 4 . Viewing H(a) as the evaluations of a linear function L 1 with H(a)(w) = L 1 (w) and letting L 2 denote the corresponding function for H(b), we have L 1 − L 2 is a non-zero polynomial of degree 1 over F 2 . By Lemma 6.6, we have that the probability that L 1 (w) − L 2 (w) = 0 is at most 1/2 and thus δ (H(a), H(b)) ≥ 1/2. But then, by the triangle inequality, we have δ (H(a), H(b)) ≤ δ(H(a), X) + δ (H(b), X) < 1 2 , giving us the desired contradiction. For the second part let δ = δ (H(a), X). Note that the probability (over L 1 ) that X(L + L 1 ) = H(a)(L + L 1 ) is at most δ since L + L 1 is uniformly distributed over all linear functions. Next note that the probability that X(L 1 ) = H(a)(L 1 ) is also at most δ (though of course this is not independent of the previous event). The probability that either of these events occurs is at most 2δ, and if neither event occurs, then we have Lemma 6.8 (Linearity testing, [16,11]). If a string X ∈ {0, 1} 2 k indexed by linear We defer the proof of this lemma to Appendix A. Roughly this construction will replace a vertex u of G by a collection of vertices {u(L)} L where L ranges over all the linear function. It will also have many 3-uniform constraints on the coloring A (which can be viewed as 4-uniform ones by repeating one of the arguments) of the form A (u(L 1 )) + A (u(L 2 )) = A (u(L 1 + L 2 )). The lemma above says that if 90% of such constraints are satisfied by A , then it must be the case that there is an a such H(a)(L) usually (for 90% of the L's) equals u(L), and so it is reasonable to view A as suggesting the coloring A(u) = D( A (u(L)) L ). Furthermore, for any fixed linear function L, we can effectively recover H(A(u))(L) by looking at A (u(L + L 1 )) − A (u(L 1 )) for a randomly chosen L 1 . This will allow us to create several other local constraints later. We now move to the constraint gadgets.
6.2. Enforcing quadratic constraints. Recall that our goal is to build "gadgets", i.e., a collection of 4-uniform constraints on a 2-coloring of some variables, that somehow verify that a 2-uniform constraint on a 2 k -coloring of two variables. Furthermore, we are assuming that the constraint is given by a collection of degree two polynomials on the 2k variables representing the colorings of the two variables. For concreteness let us fix a constraint c e on the coloring of vertices u and v. Let X 1 , . . . , X k denote the Boolean variables representing the coloring of u and Y 1 , . . . , Y k represent the Boolean variables representing the coloring of v. Further, let P 1 (X, Y ), . . . , P m (X, Y ) denote the polynomials representing the constraint c e (i.e., c e is satisfied by the coloring a, b if P j (a, b) = 0 for every j ∈ [m]).
It turns out that the Hadamard encoding brings us close to the goal of verifying such constraints. Indeed if the constraint were given by a single, homogeneous, degree one polynomial on 2k variables, then we would be done, given the Hadamard encoding gadget for the vertices u and v. To see this let P 1 (X, Y ) = P 11 (X) + P 12 (Y ) where P 11 (X) and P 12 (Y ) are both linear. Now place constraints A (u(L 1 )) + A (u(L 2 )) = A (u(L 1 + L 2 )) for every pair of linear functions L 1 , L 2 ; similar collection of constraints for v; and then finally add constraints A (u(L 3 + P 11 )) − A (u(L 3 )) + A (v(L 4 + P 12 ) − A (v(L 4 )) = 0 for every pair of linear functions L 3 and L 4 . If the decoding of a coloring A leads to a coloring A that satisfies c e , then we are set; else we find ourselves in one of two cases: Either A (u(L)) L is not 0.1-close to some encoding H(a) (or A (v(L)) L is not 0.1-close to some encoding H(b)), in which case 10% of the first class of constraints will reject, or both are 0.1-close to encodings H(a) and H(b) with (a, b) not satisfying the constraint c e , in which case P 1 (a, b) = P 11 (a)+P 12 (b) = 1. But by Lemma 6.8, with probability at most 0.2 we have P 11 (a) = A (u(L 3 + P 11 )) − A (u(L 3 )). Similarly the probability that P 12 (b) = A (v(L 4 + P 12 )) − A (u(L 4 )) is at most 0.2. Thus with the remaining probability of 0.6 we have A (u(L 3 + P 11 )) − A (u(L 3 )) + A (v(L 4 + P 12 )) − A (u(L 4 )) = P 1 (a, b) = 1, and so the latter test will reject. Thus we get an absolute constant fraction of the constraints in G corresponding to c e reject if the decoding of A does not lead to a coloring satisfying c e .
In what follows we see how to extend this idea to include a collection of degree 2 polynomials. To do so we extend the Hadamard encoding to now include the values of all degree 2 polynomials at some point a. We call this encoding the quadratic encoding. Definition 6.9. The quadratic encoding Q maps strings of length k to strings of length 2 ( k+1 2 ) . Given a string a ∈ {0, The quadratic encoding Q(a) is simply the Hadamard encoding of b.
In the case of the quadratic function encoding it is possible to view the coordinates as corresponding to homogeneous polynomials of degree 2 and thus Q(a) = q(a) q where q ranges over all degree 2 homogeneous polynomials on k variables.
Testing if a string Y ∈ 2 ( k+1 2 ) is close to the quadratic encoding of some a is a little more complex than testing Hadamard codes, but not too much more so, given the Hadamard encoding X of a. We first test to ensure Y is close to the Hadamard encoding of some string b, and then we need to test if b ij = a i a j . The main idea at this point is to consider a degree 2 homogeneous polynomial of the form L 1 (a)L 2 (a) and check to see that X and Y agree with respect to this polynomial. In the case of X its value is given by X(L 1 )X(L 2 ). On the other hand, Y 's "opinion" for the value of this polynomial is given by a majority vote over quadratic polynomial q of the difference Y (q + L 1 L 2 ) − Y (q). Analyzing this test carefully (and we will do so in the coming subsections) shows that if Y is not close to the quadratic function encoding of a when X is close to the Hadamard encoding of a, then a constant fraction of these constraints is not satisfied.
We remark that over F 2 , homogeneous polynomials essentially capture all interesting polynomials, since for every degree 2 polynomial P we can associate a homogeneous degree 2 polynomial P H and a constant β ∈ F 2 such that for every a ∈ F k 2 we have P (a) = P H (a) + β. Using this observation and the test described, we can easily extend our earlier "gadget" to the case where the constraint c e is a single degree 2 polynomial. The only remaining hurdle is that we are dealing with a system of degree 2 polynomials, and we deal with this aspect next.
We now consider the case where c e is the conjunction of polynomials P 1 , . . . , P m where m is arbitrary. Note that one obvious strategy is to repeat the exercise of testing if P j (a, b) = 0 for every j ∈ [m]. But this could lead to situations where only a fraction 1 m of the constraints (corresponding to a single unsatisfied P j ) is being unsatisfied when c e is not satisfied.
To avoid such scenarios we use once again the idea underlying the Hadamard code . Fix a coloring a, b to the pair u, v and let z j = P j (a, b). To test if z = z j j = 0 we could enumerate all the j's as above or adopt the "error-correcting" strategy, where we check to see if the wth coordinate of H(z)(w) = z·w is zero for a randomly chosen index w. If z = 0, then certainly this is zero; on the other hand, if z = 0, then the probability that this happens is equal to 1/2 (by the Schwartz-Zippel lemma). But now we note that z · w = m j=1 w j z j = m j=1 w j P j (a, b) is simply the evaluation of a single degree 2 polynomial at a, b, a condition for which we already know how to build a gadget.
Finally, while the above shows how to integrate m polynomials into one without losing in the performance of the reduction, we still need to ensure that the size of the reduction (i.e., the number of constraints) is not too large. In turn this requires a bound on m. To get an upper bound, note that without loss of generality we can assume that the P j 's are linearly independent. (If there exists λ 2 , . . . , λ m ∈ {0, 1} such that P 1 ≡ m j=2 λ j P j , then it follows that P 1 (a, b) = 0 is a redundant constraint given P j (a, b) = 0 for j ∈ {2, . . . , m}.) So we conclude that m ≤ k+2 2 . This completes the motivation for our gadget, and now we describe this gadget formally.
6.3. The actual transformation. We now give the transformation fromG K where K = 2 k to G ∈G (4) 2 .
Fix an instance G ∈G K . Let V denote the vertices of G and E its edges. For e ∈ E incident on u and v, let c e be the conjunction of degree 2 polynomials P e,1 , . . . , P e,m on the 2k variables corresponding to the coloring of u and v.
This completes the description of the gadget. While normally a gadget of such complexity would entail extremely complex analysis, in our case the analysis turns out to be quite streamlined as we see below.
6.4. Analysis. We start by taking care of the more obvious elements needed to show that the transformation from G to G is ( 3 , 1)-linear. Proposition 6.10. In the transformation of Section 6.3 from G to G , we have: (2) The constraints of G are degree 2 polynomials in at most 4 variables.
Proof. For Part 1, we inspect the construction above. It is easy to see that the size of G is only linearly large in the size of G since every vertex/constraint of G leads to 2 O(k 2 ) vertices/constraints in G . (Note that this would be an enormous blowup even for k = 10; however, it is a fixed constant for any constant k.) For Part 2, note that each constraint depends on at most 4 variables, and each constraint of them expects some polynomial of degree 1 or 2 to be zero. Indeed except for the constraints corresponding to the indices i = 6, all the constraints are of degree 1.
For Part 3, let A : V → {0, 1} k be an assignment satisfying G. Then consider the following coloring A to the vertices of G : It can be verified by inspection that this assignment satisfies every constraint c e .
We now move to the crucial part of the analysis, namely the analysis of the soundness of the transformation. The following lemma argues this by showing that if G has a coloring which leaves only a small fraction of the clauses unsatisfied, then G has a coloring which also leaves a small fraction unsatisfied. Proof. We prove the lemma for 3 = 0.001. (Note that we don't attempt to optimize the constant here.) For e ∈ E let p e denote the probability (over random choices of L 1 , L 2 , L 3 , L 4 , q 1 , q 2 , w, i from the appropriate domains) that the constraint e = e(L 1 , L 2 , L 3 , L 4 , q 1 , q 2 , w, i) is not satisfied by the assignment A . By an averaging argument, we note that the fraction of e's for which p e ≥ 3 is at most τ . We show below that for every e such that p e < 3 , the coloring A satisfies the constraint c e . This will suffice to prove the lemma.
Fix e such that p e < 3 . Let e be incident to u and v and let c e be the conjunction of constraints P j (A(u), A(v)) = 0 for j ∈ [m]. For i ∈ [7], let p e,i denote the probability (now over the remaining parameters L 1 , L 2 , L 3 , L 4 , q 1 , q 2 , w) that e = e(L 1 , L 2 , L 3 , L 4 , q 1 , q 2 , w, i) is not satisfied by A . Note that we have p e,i ≤ 7 3 for every i ∈ [7].
Linearity: Using the fact that p e,1 , p e,2 , p e,3 , and p e,4 are all at most 7 3 = 0.007 < 0.01, we conclude (using Lemma 6.8) that there exist strings a, b ∈ {0, 1} k , c ∈ {0, 1} 2k , and d ∈ {0, 1} ( 2k+1 2 ) such that A (u(L)) L is .01-close to H(a), A (v(L)) L is .01-close to H(b), A (e(L)) L is .01-close to H(c), and A (e(q)) q is .01-close to H(d). Furthermore, by the definition of the Hadamard decoding and the uniqueness of this decoding (Proposition 6.7), we have that A(u) = a and A(v) = b. It suffices to prove that P j (a, b) = 0 for every j ∈ [m], and we will do so below. This will involve relating a, b, c, d to each other and then using the constraints corresponding to i = 7. a, b, c: Suppose c = (a, b). We will show that in this case the probability that the constraint c e for e = e(L 1 , L 2 , L 3 , L 4 , q 1 , q 2 , w, 5) is unsatisfied is at least .47 > 7 3 , which contradicts our bound on p e,5 . Recall that c e is satisfied if A (u(L 1 )) + A (v(L 2 )) = A (e(L 12 )). Since A (u(L)) L is 0.01 close to H(a), we have that the probability (over L 1 ) that A (u(L 1 )) = H(a)(L 1 ) is at most .1. Similarly we have that the probability (over L 2 ) that A (v(L 2 )) = H(b)(L 2 ) is also at most .01. Finally since L 12 is a random function chosen uniformly among all linear functions mapping {0, 1} 2k to {0, 1}, we also have that the probability (over L 12 ) that A (e(L 12 )) = H(c)(L 12 ) is at most .01. Finally we note that if c = (a, b), then the probability (over L 12 ) that H(c)(L 12 ) = H(a, b)(L 12 ) is at most 1/2. By the union bound the probability that at least one of the above events occurs is at most .53. Thus with probability at least .47 none of the events listed above occur, and then we have and the constraint e rejects, as claimed. We conclude thus that c = (a, b).

Consistency of c and d:
Again suppose d ij = c i c j for some i ≤ j. We now claim that the probability (essentially over L 3 , L 4 and q 1 ) that the constraint c e , for e = e(L 1 , L 2 , L 3 , L 4 , q 1 , q 2 , w, 6), is unsatisfied is at least 0.21 > 7 3 . Recall that c e is satisfied if A (e(L 3 ))A (e(L 4 )) = A (e(q 1 + L 3 L 4 )) − A (e(q 1 )).
As in the previous case, we conclude that the probability of at least one of the events We first note that f is not identically zero (since d ij = c i c j for some i, j). Viewing f as a polynomial in only the X's (with coefficients from the field of rational functions in Y ), we see that f is of degree 1. Hence by Lemma 6.6 we have that f (α, Y ) is non-zero with probability at least 1/2. Furthermore, if so, then f (α, Y ) is a degree 1 polynomial in Y and so (again using Lemma 6.6) f (α, β) is non-zero with probability at least 1/2. Thus putting the two together we get that f (α, β) is non-zero with probability at least 1/4, or equivalently it is zero with probability at most 3/4. Thus with probability that any of the events listed above occurs is at most .79. Thus the probability that none of the events occur is at least .21, and in such case we have and the constraint c e is unsatisfied. We conclude thus that d ij = c i c j . As a consequence we have that for a random homogeneous degree 2 polynomial q, A (e(q)) = Q(c)(q) with probability at most .01.
Satisfaction of c e : We move to the last step of our analysis. Assume for contradiction that P j (a, b) = P j (c) = 0 for some j ∈ [m]. Consider a random constraint e = e(L 1 , . . . , w, 7). Note that c e is satisfied iff A (e(q 1 + P H )) − A (e(q 1 )) + β = 0 where P H and β were chosen so that j w j P j (c) = P H (c) + β. First note that the probability that j w j P j (c) = 0 is at most 1/2 (over the choice of w). We also have A (e(q 1 )) = q 1 (c) with probability at most .01 and A (e(q 1 + P H )) = (q 1 + P H )(c) is also at most .01. Thus the probability that none of the above events happen is at least .48, and in such case we have A (e(q 1 + P H )) − A (e(q 1 )) + β = (q 1 + P H )(c) − (q 1 )(c) + β = P H (c) + β = 0 and the constraint c e is unsatisfied. Thus we have that the colors a = A(u) and b = A(v) satisfy the constraint c e whenever p e < 3 , and this holds for 1−τ fraction of the edges e as desired.
Proof of Lemma 6.3. The lemma holds for 3 as given by Lemma 6.11. The transformation is the one given in Section 6.3. The fact that it is satisfiability-preserving and linear-size-preserving follows from Proposition 6.10. Finally, Lemma 6.11 implies that if the unsatisfiability of the source instance G is at least τ , then the unsatisfiability of the transformed instance G is at least 3 · τ .

Conclusion
We hope the reader finds the above description to be somewhat useful and motivating when reading Dinur's new approach to construction of PCPs. We remark that the earlier algebraic approaches, while technically much more complicated, do have some appealing high level views. The reader is pointed to the work of Ben-Sasson and Sudan [15] to get a sense of some of the work in the older stream.
Moving on beyond the specific proofs and constructions used to get probabilistically checkable proofs, we hope that the notion itself is appealing to the reader. The seemingly counterintuitive properties of probabilistically checkable proofs highlight the fact that the "format" in which a proof is expected is a very powerful tool to aid the person who is verifying proofs. Indeed for many computer-generated proofs of mathematical theorems, this notion may ease verifiability, though in order to do so, PCPs need to get shorter than they are and the verification scheme simpler than it is. Dinur's work helps in this setting, but much more needs to be done.
And finally, moving beyond the notion of proofs, we also hope this article reminds the reader once more of a fundamental question in logic and computation, and indeed for all mathematics: Is P=NP? Can we really replace every mathematician by a computer? If not, would it not be nice to have a proof of this fact?
We now express the quantity E L 1 ,L 2 [X(L 1 )X(L 2 )X(L 1 + L 2 )] in terms of the Fourier coefficients. We have B. Expanders, eigenvalues and random walks. The main goal of this section is to prove Proposition 5.11. A version of this proposition appears in the original paper of Dinur [19]. Our version differs only in that we work with walks on directed graphs. The proof involves algebraic properties of expander graphs, which we describe next. Definition B.1 (Eigenvalues of a graph). Let G be a d-regular graph with n vertices. The adjacency matrix of G is the matrix A(G) = (a vw ) whose rows and columns are indexed by elements of V (G) and a vw is the number of edges of the form (v, w). Then, A(G) is a symmetric n × n matrix and has n real eigenvalues. The largest eigenvalue of A(G) is d (corresponding to all the 1s eigenvector 1), and all eigenvalues are bounded by d in absolute value. We denote these eigenvalues by λ 1 (G), λ 2 (G), . . . , λ n (G), where d = λ 1 (G) ≥ λ 2 (G) ≥ · · · ≥ λ n (G) ≥ −d. Then, the second eigenvalue of G is defined to be λ(G) = max{|λ 2 |, |λ n |}.
Also, there is an orthonormal basis {v 1 , v 2 , . . . , v n } of R n , where v i is an eigenvector of A(G) corresponding to λ i (G).
Remark. If we assume that each vertex of the d-regular graph has at least d 2 selfloops, then all eigenvalues of G are non-negative and the second eigenvalue of G is λ 2 (G).