Theory of Computing, Volume 1 (2005), pp. 119–148 http://theoryofcomputing.org

Query Efficient PCPs with Perfect Completeness

Johan Håstad^{∗}  Subhash Khot^{†}

Received: October 21, 2004; revised: August 23, 2005; published: September 28, 2005.

Abstract: For every integer k > 0, and an arbitrarily small constant ϵ > 0, we present a PCP characterization of NP where the verifier uses logarithmic randomness, non-adaptively queries 4k + k^{2} bits in the proof, accepts a correct proof with probability 1, i. e., it has perfect completeness, and accepts any supposed proof of a false statement with probability at most 2^{−k^{2}} + ϵ. In particular, the verifier achieves optimal amortized query complexity of 1 + δ for arbitrarily small constant δ > 0. Such a characterization was already proved by Samorodnitsky and Trevisan (STOC 2000), but their verifier loses perfect completeness and their proof makes an essential use of this feature.

By using an adaptive verifier, we can decrease the number of query bits to 2k + k^{2}, equal to the number obtained by Samorodnitsky and Trevisan. Finally we extend some of the results to PCPs over non-Boolean alphabets.

∗Work done while visiting the Institute for Advanced Study, supported by NSF grant CCR-9987077. †Work done while the author was at Princeton University.

ACM Classification: F 2.2

AMS Classification: 68Q25

Key words and phrases: Computational complexity, approximation algorithms, probabilistically checkable proofs, PCP, inapproximability, amortized query bits, perfect completeness, amortized query bits

Authors retain copyright to their papers and grant “Theory of Computing” unlimited rights to publish the paper electronically and in hard copy. Use of the article is permitted as long as the author(s) and the journal are properly acknowledged. For the detailed

copyright statement, see http://theoryofcomputing.org/copyright.html.

\begin{matrix}c \\ ◯ \end{matrix} 2005 Johan Håstad and Subhash Khot

J. Håstad and S. Khot

1 Introduction

The celebrated PCP Theorem ([2], [1]) gives a way of writing proofs for (purported) NP statements such that the proofs can be checked very efficiently by a probabilistic verifier. The verifier needs a very limited amount of random bits and reads only a constant number of bits from the proof. Moreover, a correct statement always has a proof that is accepted with probability 1 (or close to 1) and any proof of an incorrect statement is accepted only with a tiny probability (called error probability or soundness).

PCPs have surprising connections, first discovered by Feige et al. [5], to inapproximability results, i. e., results showing that computing even approximate solutions to some NP-complete problems is hard. The discovery of the PCP Theorem opened up a whole new fascinating direction for proving various inapproximability results. In the last decade or so, quantitative improvement in the efficiency of PCP verifiers has led to (in many cases optimal) inapproximability results for many optimization problems ([3], [4], [14], [13], [12], [6]). For different applications, different aspects of the given PCP need to be optimized. For a detailed discussion of various parameters we refer to [3].

In the current paper we are mostly concerned with making efficient use of queries, i. e., to obtain very strong PCPs where the verifier reads very few symbols in the proof. More specifically, we are interested in the trade-off between the number of queries and the error probability.

Samorodnitsky and Trevisan [12] obtained very strong results along these lines, giving a PCP where the verifier reads 2k + k^{2} bits, almost always accepts a correct proof of a correct statement and accepts a proof of an incorrect statement with probability only marginally larger than 2^{−k^{2}} . This is a very impressive result in that each read bit essentially decreases the probability of being fooled by a factor of 2. Their verifier achieves amortized query complexity of 1 + δ for any δ > 0 which is optimal (see [3]). The amortized query complexity, when we (almost) always accept a correct proof, is formally defined as the ratio between the number of queries (2k +k^{2} in this case) and the logarithm of inverse of the error probability (k^{2} in this case).

The fact that the verifier sometimes rejects a correct proof of a correct statement is called imperfect completeness and in their construction Samorodnitsky and Trevisan make essential use of this property of the verifier. For many reasons it is preferable to have perfect completeness. Firstly, it is natural to have a proof system where a correct proof of a correct statement is always accepted. Secondly, perfect completeness is sometimes essential to obtain further results. Some inapproximability results such as graph coloring sometimes make essential use of perfect completeness and when using a given protocol as a subprotocol in future protocols, perfect completeness, to say the least, simplifies matters.

Several results in the past have focused on achieving PCPs with perfect completeness and this task many times turns out to be harder than obtaining corresponding PCPs without this property. For instance, Håstad shows that 3SAT and 4-Set Splitting are hard to approximate within ratio \frac{8}{7} + ϵ. These results follow from the basic 3-bit PCP of [13] establishing hardness for approximating the number of satisfied linear equations mod 2. To extend these results to satisfiable instances, however, requires a new PCP construction and a technically more complicated proof.

The main result of the current paper is to extend the result of Samorodnitsky and Trevisan to include perfect completeness.

Query Efficient PCPs with Perfect Completeness

Theorem 1.1. For any integer k > 0 and any ϵ > 0, any language in NP has a PCP verifier that queries 4k + k^{2} bits, has perfect completeness and accepts a proof of an incorrect statement with probability at most 2^{−k^{2}} + ϵ.

Our result is based on a basic non-linear test which reads 5 bits (b_{1},b_{2},b_{3},b_{4},b_{5}) from the proof and accepts if b_{1} = b_{2}⊕ b_{3}⊕ (b_{4}∧ b_{5}). We call this constraint Tri-Sum-And and let MAX-TSA be the problem of satisfying the maximum number of such constraints. We have the following theorem.

Theorem 1.2. For any ϵ > 0, it is NP-hard to distinguish satisfiable instances of Max-TSA from those where it is only possible to simultaneously satisfy a fraction \frac{1}{2} + ϵ of the constraints.

The choice to study Tri-Sum-And is somewhat arbitrary but guided by our goal to achieve perfect completeness while keeping the analysis simple. To get perfect completeness we need a nonlinear predicate while the analysis is greatly aided by having as much linearity as possible present in the predicate. These two conflicting requirements led to the choice of Tri-Sum-And.

Note that Theorem 1.2 is tight for Max-TSA in that a random assignment satisfies half the constraints. There are stronger results for other constraints on 5 bits and in particular Guruswami et al. [7] give a different predicate for which \frac{1}{2} can be improved to \frac{7}{16}.

We then iterate the basic test underlying Theorem 1.1 in a way similar to that used by Samorodnitsky and Trevisan, where they iterate the basic 3-bit test by Håstad. We present two iterated tests: The first, which we call the “complete bipartite graph PCP,” is analyzed in a way analogous to the Samorodnitsky-Trevisan analysis and the second, which we call the “almost disjoint sets PCP,” is analyzed in a way analogous to how Håstad and Wigderson [15] analyzed the test of Samorodnitsky and Trevisan.

By a standard reduction the PCP results imply the following theorem.

Theorem 1.3. The Boolean constraint satisfaction problem on k variables is hard to approximate within ratio 2^{k−O(\sqrt{k})} on satisfiable instances.

This should be contrasted with the approximation algorithm by Trevisan [16] that shows that it is possible to approximate the Boolean constraint satisfaction problem on k variables within O(2^{k}/k) on satisfiable instances.

A test is called non-adaptive if which bits to read are decided before the first bit is read and hence this set is independent of the actual proof. All the above mentioned PCPs are non-adaptive which is in fact necessary to obtain Theorem 1.3.

If we allow adaptive tests then by making an iterated version of a test in [7] we can get essentially the same parameters as Samorodnitsky and Trevisan and thus simply gain perfect completeness.

Theorem 1.4. For any integer k > 0 and any ϵ > 0, any language in NP has an adaptive PCP verifier that queries 2k + k^{2} bits, has perfect completeness and accepts a proof of an incorrect statement with probability at most 2^{−k^{2}} + ϵ.

If we convert the test to be non-adaptive, this test would read 2k +2k^{2} different bits and hence this result does not strictly dominate Theorem 1.1. We extend some of our results to non-Boolean domains and in particular we have the following theorem.

Theorem 1.5. For every prime p, the constraint satisfaction problem on k variables over an alphabet of size p is hard to approximate within ratio p^{k−O(\sqrt{k})} on satisfiable instances.

We hope that our results will be useful in the future to prove strong hardness results for approximate graph coloring. One such result by Khot [9] is

Theorem 1.6 ([9]). There is an absolute constant c > 0 such that it is NP-hard to color a k-colorable graph with k^{clogk} colors.

Actually this result can be proved from the original form of the Samorodnitsky-Trevisan result and perfect completeness is not strictly required. But using our PCP with perfect completeness, this result becomes more straightforward. On a related note one can observe that perfect completeness is essential in the hypergraph coloring results by Guruswami, Håstad and Sudan [6], and in general it is a subtle problem to determine which coloring inapproximability results require perfect completeness in the underlying PCP.

1.1 Overview of the paper

This is the complete version of the extended abstract [8]. The paper is organized as follows. Section 2 introduces techniques used in this paper. In Section 3 we give our results for the Boolean case: Section 3.1 gives our basic 5-bit test, and Section 3.2 describes our iterated tests. Section 4 extends some of the results of Section 3 to non-Boolean domains. Section 5 concludes with a few remarks.

2 The general setup

In this section we provide the necessary background.

2.1 Notation

Throughout the paper, we have Boolean functions in ±1 notation with −1 as logical true. We use multiplication to denote exclusive-or, ∧ for the logical AND function. As we use −1 to denote true we have

x ∧ y = AND(x,y) = \frac{1 + x + y − xy}{2} .

Our default is that AND is highest level connective and in particular

xy ∧ zw = (xy) ∧ (zw) .

Addition is used only over the real and complex numbers.

2.2 The 2-prover protocol

Many efficient PCPs, such as the one given in [12], are conveniently analyzed using the formalism of an outer and inner verifier. This could also be done here, but to avoid too much formalism we give a more explicit analysis. Using the results of [1] (as explicitly done in [4]) one can prove that there is a constant c < 1 such that it is NP-hard to distinguish satisfiable 3-SAT formulas from those where only a fraction c of the clauses can be simultaneously satisfied by any assignment. This formula can furthermore have the property that any clause is of length exactly 3 and any variable appears in exactly 5 clauses.

Given a 3-SAT formula φ = C_{1}∧C_{2}...∧C_{m}which is either satisfiable or where one can only satisfy a fraction c of the clauses, one can design a two-prover interactive proof system with verifier V as follows.

Basic two-prover protocol

1. V chooses a clause C_{k} uniformly at random and a variable x_{j}, again uniformly at random, appearing in C_{k}. V sends k to prover P_{1} and j to prover P_{2}.

2. V receives a value for x_{j} from P_{2} and values for all variables appearing in C_{k} from P_{1}. V accepts if the two values for x_{j} agree and the clause C_{k} is satisfied.

It is not difficult to see that if a fraction c of the clauses can be satisfied simultaneously then the optimal strategy of P_{1} and P_{2} convinces V with probability (2 + c)/3. Thus it is NP-hard to distinguish the case when this probability is 1 and when it is some constant strictly smaller than 1. Note also that if we start with a formula where each variable appears the same number of times, V could first choose a random variable and then a random clause containing that variable and get the same distribution.

To make the gap larger, one runs this protocol u times in parallel resulting in the following protocol.

u-parallel two-prover protocol, 2PP(u)

1. V chooses u clauses (C_{k_{i}})_{i=1}^{u} uniformly at random and for each i, V chooses a variable x_{j_{i}}, again uniformly at random, appearing in C_{k_{i}}. V sends (k_{i})_{i=1}^{u} to prover P_{1} and (j_{i})_{i=1}^{u} to prover P_{2}.

2. V receives values for (x_{j_{i}})_{i=1}^{u} from P_{2} and values for all variables appearing in (C_{k_{i}})_{i=1}^{u} from P_{1}. V accepts if the two values for x_{j_{i}} agree for each i and all the picked clauses are satisfied.

We let U denote the set of variables sent to P_{2}, i. e., (x_{j_{i}})_{i=1}^{u} while the set of variables that P_{1} gives values to is denoted by W. Note that U ⊂ W.

By the fundamental result by Raz [11], the probability that the verifier accepts in 2PP(u) when only a constant fraction c < 1 of the clauses can be simultaneously satisfied is bounded by d_{c}^{u} for some absolute constant d_{c} < 1. Let us formulate these properties for future reference.

Theorem 2.1. Let 2PP(u) be the u parallel version of the basic two-prover protocol. Then if only a fraction c < 1 of the clauses of φ can be simultaneously satisfied, then no strategy of P_{1} and P_{2} can make the verifier accept with probability greater than d_{c}^{u}. Here d_{c} < 1 is a constant that only depends on c.

2.3 Long codes

To turn the protocol 2PP(u) into a written proof that can be checked very efficiently, it is natural to, for each question to either P_{1} or P_{2}, write down the answer in coded form. As many other papers we use the long code introduced by Bellare et al. [3].

Definition 2.2. The long code of an assignment x ∈ {−1,1}^{t} is obtained by writing down for each function f : {−1,1}^{t} → {−1,1}, the value f(x).

Thus the long code of a string of length t is a string of length 2^{2^{t}}. Note that even though a prover is supposed to write down a long code for an assignment a cheating prover might write down a string which is not the correct long code of anything. We analyze such arbitrary tables by Fourier expansion.

2.3.1 Fourier analysis

In this section, we explain the basics of the Fourier method. Let

ℱ = {f | {−1,1}^{t} → {−1,1}}

and consider the vector space of all “tables” A : ℱ → ℝ. Here the addition of two tables is defined as pointwise addition and the dimension of this vector space is |ℱ| = 2^{2^{t}}. One can define a natural inner product on this space by letting the inner product of two tables A_{1} and A_{2} be

⟨A_{1},A_{2}⟩ = 2^{−2^{t}} ∑_{f} A_{1}(f)A_{2}(f) .

For α ⊆ {−1,1}^{t}, let χ_{α} be a Boolean-valued (i. e., {−1,1}-valued) table defined as

χ_{α} (f) = ∏_{x∈α} f(x) ∀ f ∈ ℱ .

The χ_{α} are called characters. The characters are multiplicative, i. e.,

χ_{α} (f_{1}f_{2}) = χ_{α} (f_{1})χ_{α} (f_{2}) .

The characters are in fact symmetric in α and f but as we have used set notation for α we have

χ_{α_{1}}(f)χ_{α_{2}}(f) = χ_{α_{1}⊕α_{2}} (f)  (2.1)

where α_{1} ⊕ α_{2} is the exclusive-or of the characteristic vectors of the sets α_{1} and α_{2}. Put differently, α_{1}⊕ α_{2} is the set which is the symmetric difference of α_{1} and α_{2}.

The set of characters (there are 2^{2^{t}} of them) forms an orthonormal basis for the vector space. Thus any table A can be expressed as

A(f) = ∑_{α⊆{−1,1}^{t}} Â_{α}χ_{α} (f) ,

where Â_{α} are real numbers called Fourier coefficients; they can found as

Â_{α} = ⟨A,χ_{α} ⟩ = 2^{−2^{t}} ∑_{f} Â(f)χ_{α} (f) .

If A is Boolean valued, we have Parseval’s identity ∑_{α} Â_{α}^{2} = 1. If A is indeed a correct long code of a string x^{(0)} then Â_{{x^{(0)}}}= 1 while all the other Fourier coefficients are 0.

In our protocols we pick a function uniformly and then often perform an analysis using the Fourier expansion. The following lemma is simple but powerful.

Lemma 2.3. Assume that f is picked with the uniform distribution then for α ≠ ∅,

E_{f} [χ_{α} (f)] = 0

while

E_{f} [χ_{∅}(f)] = 1 .

Using this lemma together with (2.1) enables us to compute the expected value of products of characters in a simple way.

We can, to a limited extent, put some restrictions on the tables produced by the prover.

Definition 2.4. A table A is folded over true if A(f) = −A(−f) for any f.

Definition 2.5. A table A is conditioned upon a function h: {−1,1}^{t} → {−1,1}, if A(f) = A(f ∧ h) for any f.

To make sure that an arbitrary table is folded we access the table as follows. For each pair (f,−f) we choose (in some arbitrary but fixed way) one representative. If f is chosen, then if the value of the table is required at f it is accessed the normal way by reading A(f). If the value at −f is required then in this case also A(f) is read but the result is negated. If −f is chosen from the pair the procedures are reversed.

Similarly we can make sure that a given table is properly conditioned by always reading A(f ∧ h) when the value for f is needed. Folding over true and conditioning can be done at the same time.

Let us now give the consequences of folding and conditioning for the Fourier coefficients. The proofs are easy and left to the reader but they can also be found in [14].

Lemma 2.6. If A is folded over true and Â_{α} ≠ 0 then |α| is odd and in particular α is non-empty.

Lemma 2.7. If A is conditioned upon h and Â_{α} ≠ 0 then for every x ∈ α, h(x) is true (i. e., h(x) = −1).

We will be working with sets U and W with the property that U ⊂ W and we let π : {−1,1}^{W} → {−1,1}^{U} be the projection operator that maps an assignment on W to its subassignment on U. For every β ⊆ {−1,1}^{W}, let π(β) ⊆ {−1,1}^{U} be defined as

π(β) = {π(y) | y ∈ β} .

We also need an operator π_{2} defined as follows : for any β ⊆ {−1,1}^{W}, π_{2}(β) ⊆ {−1,1}^{U} is the set of those x which have an odd number of preimages in β, i. e.,

π_{2}(β) = {x | x ∈ {−1,1}^{U}, |β ∩ π^{−1} (x)| is odd} .

Note that these projection operators depend on the identities of U and W but as no confusion is likely to arise we suppress this fact.

A function f with domain {−1,1}^{U} can naturally be extended to domain {−1,1}^{W}by simply using the value f(π(y)). We use the same symbol to denote this extended function and hope that no confusion arises. We have the following simple lemma.

Lemma 2.8. Let β ⊆ {−1,1}^{W}, U ⊆ W and f : {−1,1}^{U} → {−1,1}, then

χ_{β}(f) = χ_{π_{2}(β)}(f) .

3 Efficient PCPs for Boolean domains

In this section we convert 2PP(u) to a PCP. We eliminate the provers by asking the prover to write down the answer to each question (in encoded form). Furthermore, remember that U is the set of u variables which are sent to P_{2} in the two-prover protocol. For each possible set U we ask the prover to write a table, A_{U}, which is supposed to be the long code of the answer by P_{2} on question U. We assume that A_{U} is folded over true.

Similarly W is the set of variables in the u clauses sent to P_{1} and let φ_{W} be the conjunction of the clauses chosen. In the PCP we have a table, B_{W}, which is a supposed to be the long code of the answer of P_{1} on question W. We assume that B is folded over true and conditioned upon φ_{W}.

3.1 Our basic test

We have the following basic test, defined using the conventions above.

Basic PCP

1. V chooses U, W and φ_{W} as in 2PP(u).

2. V chooses two functions f and f′on U uniformly at random (i. e., f,f′: {−1,1}^{U} → {−1,1}).

3. V chooses two functions g and g′on W uniformly at random (i. e., g,g′: {−1,1}^{W}→ {−1,1}). V defines a third function h by setting, for each y ∈ {−1,1}^{W}, h(y) = g(y)f(π(y))(g′(y)∧f′(π(y))).

4. V accepts iff B_{W}(h) = B_{W}(g)A_{U}(f)(B_{W}(g′) ∧ A_{U}(f′)).

We have the basic completeness lemma.

Lemma 3.1. The completeness of the basic PCP is 1.

Proof. In a correct proof of a correct theorem each table is a correct long code of a restriction of a given global assignment to the set in question. If we denote this assignment by z then B_{W}(h) = h(π^{W}(z)) where π^{W} is the projection onto W and similarly for the other involved functions. The completeness now follows from the definition of h.

The main problem is to establish soundness.

Lemma 3.2. If the verifier in the basic test accepts with probability (1+δ)/2 then there exists a strategy for P_{1} and P_{2} in 2PP(u) that makes the verifier accept with probability δ^{O(1)}. In particular if the protocol 2PP(u) is chosen to have sufficiently small soundness (by choosing u large enough), then the verifier in the basic test accepts with probability at most (1 + δ)/2.

Proof. For readability we drop the subscripts and use A instead of A_{U} and B instead of B_{W}. Consider the expression

\frac{1 + B(h)B(g)A(f)(B(g′) ∧ A(f′))}{2} .

Theory of Computing, Volume 1 (2005), pp. 119–148 126

This expression is 1 if the test accepts and 0 otherwise. Hence the probability of acceptance for the test is the expectation of this expression over the choice of f,f′,g,g′,U, and W. The hypothesis of the lemma implies that

E_{f,f′,g,g′,U,W}[B(h)B(g)A(f)(B(g′) ∧ A(f′))] = δ .  (3.1)

Fix U,W,f′and g′and let us study

E_{f,g}[B(h)B(g)A(f)] .

Replacing each function by its Fourier expansion we see that this equals

∑_{β_{1},β_{2},α} B̂_{β_{1}}B̂_{β_{2}}Â_{α}E_{f,g}[χ_{β_{1}}(fg(f′∧ g′))χ_{β_{2}}(g)χ_{α} (f)]

which, using (2.1) and Lemma 2.8, can be simplified to

∑_{β_{1},β_{2},α} B̂_{β_{1}}B̂_{β_{2}}Â_{α}E_{f,g}[χ_{β_{1}}(f′∧ g′)χ_{β_{1}⊕β_{2}} (g)χ_{π_{2}(β_{1})⊕α} (f)] .  (3.2)

Using Lemma 2.3, the inner expected value is 0 unless β_{1} = β_{2} = β and π_{2}(β) = α and otherwise it is 1. Thus the expected value in (3.2) equals

∑_{β} B̂_{β}^{2}Â_{π_{2}(β)}χ_{β}(f′∧ g′) ,

and hence we need to analyze

E_{f′,g′}[χ_{β}(f′∧ g′)(B(g′) ∧ A(f′))] .  (3.3)

We have a ∧ b = \frac{1}{2}(1 + a + b − ab) and thus (3.3) equals

\frac{1}{2} (E[χ_{β}(f′∧ g′)] + E[χ_{β}(f′∧ g′)B(g′)] + E[χ_{β}(f′∧ g′)A(f′)] − E[χ_{β}(f′∧ g′)B(g′)A(f′)]) . (3.4)

Fix the value of f′and let

β′= {y | y ∈ β ∧ f′(π(y)) = −1} .

When averaging over g′, the first and third expected values in (3.4) are 0 unless β′= ∅ while the second and the fourth expected values equal B̂_{β′}and B̂_{β′}A(f′), respectively. To estimate the first and third terms we note that the probability, over the choice of f′, that β′is empty is 2^{−|π(β)|} . For the other terms we set

α = {x | x ∈ π(β) ∧ f′(x) = −1}

and use the Cauchy-Schwarz inequality to obtain

E_{f′}[|B̂_{β′}|] = 2^{−|π(β)|} ∑_{α⊆π(β)} |B̂_{β∩π^{−1} (α)} | ≤ 2^{−|π(β)|/2} ( ∑_{α⊆π(β)} B̂_{β∩π^{−1} (α)}^{2} ) ^{1/2} ≤ 2^{−|π(β)|/2} .  (3.5)

This implies that we get an overall upper bound on the left hand side of (3.1) as

E_{U,W}[ ∑_{β} B̂_{β}^{2}|Â_{π_{2}(β)}|(2^{−|π(β)|} + 2^{−|π(β)|/2} )] ≤ E_{U,W}[ ∑_{β} B̂_{β}^{2}|Â_{π_{2}(β)}|2^{1−|π(β)|/2} ] ,  (3.6)

and hence this expression is at least δ. We use this to establish good strategies for P_{1} and P_{2}. We first establish that some parts of the given sum are small. We have the following result from [14, Lemma 6.9]

E_{U}[|π(β)|^{−1} ] ≤ |β|^{−c} ,  (3.7)

where c is a constant and in fact c = \frac{1}{35} is possible. Note that the expectation is taken only over U and is true for any W.

Let S_{δ} = (4(6 + 2logδ^{−1} )/δ)^{1/c} and consider any β of size at least S_{δ}. Since

E[|π(β)|^{−1} ] ≤ δ/4(6 + 2logδ^{−1} )^{−1} ,

we conclude that the probability that |π(β)| ≤ (6 + 2logδ^{−1} ) is upper bounded by δ/4. Thus for any β of size at least S_{δ} we have

E_{U}[2^{1−|π(β)|/2} ] ≤ Pr[|π(β)| ≤ (6 + 2logδ^{−1} )] + 2^{2+logδ^{−1}} ≤ \frac{δ}{4} + \frac{δ}{4} = \frac{δ}{2}

and hence discarding terms with |β| ≥ S_{δ} in (3.6) still keeps a sum of expected value at least δ/2.

Furthermore since ∑_{β} B̂_{β}^{2} = 1 we can discard any term with |Â_{π_{2}(β)}| ≤ δ/4 and not reduce the sum by more than δ/4. We conclude that the sum which is the right hand side of (3.6) is at least δ/4 even if we restrict summation to β of size at most S_{δ} and such that |Â_{π_{2}(β)}| ≥ δ/4.

Now consider the following strategy for the provers P_{1} and P_{2}. On receiving W, P_{1} chooses β with probability B̂_{β}^{2} and returns a random y ∈ β. Similarly on receiving a U, P_{2} chooses α with probability Â_{α}^{2} and returns a random x ∈ α. We note that since A,B are folded over true, by Lemma 2.6, the sets α and β selected by the provers are always nonempty. Also, since B is conditioned upon φ_{W}, by Lemma 2.7, every y ∈ β satisfies the formula φ_{W}. The success-probability of the given strategy is at least

E_{U,W}[ ∑_{β} B̂_{β}^{2}Â_{π_{2}(β)}^{2}|β|^{−1} ] .  (3.8)

If we restrict summation to |β| ≤ S_{δ} and |Â_{π_{2}(β)}| ≥ δ/4, (3.8) is at least

S_{δ}^{−1} δ/4 E_{U,W}[ ∑_{β;|β|≤S_{δ},|Â_{π_{2}(β)}|≥δ/4} B̂_{β}^{2}|Â_{π_{2}(β)}|]

and, by the above reasoning, this expected value is at least δ/4 and we get a lower bound S_{δ}^{−1} (δ/4)^{2} for the success probability of the provers. This completes the proof of Lemma 3.2.

The basic test reads 5 bits (b_{1},b_{2},b_{3},b_{4},b_{5}) of the proof and checks whether b_{1}b_{2}b_{3}(b_{4} ∧ b_{5}) = 1 which is same as b_{1} = b_{2} ⊕ b_{3} ⊕ (b_{4} ∧ b_{5}) in {0,1} notation. Theorem 1.2 now follows by a standard procedure of replacing the bits in the proof by variables and asking for a proof that maximizes the acceptance probability.

3.2 Iterated tests

We now extend our basic test in a query efficient way. We pick one set U and on it we pick k functions (f_{i})_{i=1}^{k} and k functions (f′_{j})_{j=1}^{k} and k sets (W_{l})_{l=1}^{k} each with its pair of functions (g_{l},g′_{l}). Each W_{l} is picked uniformly from the set of possible companion in 2PP(u) to the already picked U. Thus for each l, (U,W_{l}) appears with the same probability as (U,W) in 2PP(u). Note that W_{l} is not independent of W_{l′} for l ≠ l′as they are companions of the same U.

We perform the basic test for a certain set of quadruples (f_{i},f′_{j},g_{l},g′_{l}). We give strong analyses in two cases each utilizing k^{2} quadruples. One is given by the constraint i = j and is analyzed very much as Samorodnitsky and Trevisan [12] analyzed their tests. We call it the “complete bipartite PCP”.

The other set of k^{2} quadruples is given by all triples (i,j,l) such that i + j + l = 0 modk. The key property of this set of triples is that any two different triples have at most one coordinate in common. Hence we call it the “almost disjoint sets PCP”. This analysis, done in the style of Håstad and Wigderson [15], is substantially simpler and hence we give this proof first.

In either case we get a test that reads 4k + k^{2} bits, has perfect completeness and soundness only marginally higher than 2^{−k^{2}} . Theorem 1.1 can therefore be obtained either from Theorem 3.3 below which analyzes the almost disjoint sets PCP or Theorem 3.4 which analyzes the complete bipartite test.

3.2.1 The almost disjoint sets PCP

We first define the test which is an iteration of the basic test studied in the last section. The test depends on the parameter u used in 2PP(u) but we keep this dependence implicit to simplify notation.

textbf k-iterated almost disjoint sets PCP

1. V chooses U as in 2PP(u).

2. V chooses independently k sets (W_{l})_{l=1}^{k}, that can appear with U in 2PP(u). Each W_{l} is chosen with the distribution induced by 2PP(u), i. e., the distribution of the pair U,W_{l} is the same as the distribution of U,W in 2PP(u).

3. V chooses 2k functions (f_{i})_{i=1}^{k} and (f′_{j})_{j=1}^{k} on U uniformly at random.

4. For each l, 1 ≤ l ≤ k, V chooses two functions g_{l} and g′_{l}on W_{l} uniformly at random.

5. For each triple i,j,l such that i + j + l ≡ 0 modk define a function h_{ijl} by setting for each y ∈ {−1,1}^{W_{l}}, h_{ijl}(y) = g_{l}(y)f_{i}(π(y))(g′_{l}(y) ∧ f′_{j}(π(y))).

6. V accepts iff B_{W_{l}}(h_{ijl}) = B_{W_{l}}(g_{l})A_{U}(f_{i})(B_{W_{l}}(g′_{l}) ∧ A_{U}(f′_{j})) for all i + j + l ≡ 0 modk.

We have the following theorem.

Theorem 3.3. The k-iterated almost disjoint sets test has completeness 1 and soundness 2^{−k^{2}} + d_{c}^{Ω(u)}, where d_{c} is the constant from Theorem 2.1 and u is the parameter of the underlying 2-prover protocol.

Proof. The completeness follows from that of the basic test and we need to analyze the soundness. For readability let us replace A_{U} by A and B_{W_{l}} by B_{l}. Let Z_{0} denote the set of all triples (i,j,l) such that i + j + l ≡ 0( modk).

Let Acc(i,j,l) be a variable that indicates whether the test given by the triple (i,j,l) accepts, taking the value 1 if it does and −1 otherwise. Clearly

Acc(i,j,l) = B_{l}(h_{ijl})B_{l}(g_{l})A(f_{i})(A(f′_{j}) ∧ B_{l}(g′_{l})) .

Consider

∏_{(i,j,l)∈Z_{0}} \frac{1 + Acc(i,j,l)}{2} = 2^{−k^{2}} ∑_{S⊆Z_{0}} ∏_{(i,j,l)∈S} Acc(i,j,l) .  (3.9)

This number equals 1 if the test accepts and is 0 otherwise and thus its expected value is the probability that the test accepts. The term in the right hand side sum with S = ∅ equals 1 and to establish the theorem it is sufficient to establish that any other term is bounded by d_{c}^{Ω(u)}. Let Π_{S} be the term corresponding to S ≠ ∅ and let T_{S} be the expectation of Π_{S}. We go on to establish strategies for P_{1} and P_{2} which makes the verifier in 2PP(u) accept with probability |T_{S}|^{O(1)}. This is clearly sufficient to establish the theorem.

Suppose without loss of generality that (k,k,k) ∈ S and let us fix the values of f_{i}, i ≠ k, f′_{j}, j ≠ k and (W_{l},g_{l},g′_{l}) for l ≠ k in such a way that the conditional expectation of Π_{S} remains at least T_{S}. As the sets in Z_{0} only intersect in one point we can, up to a factor ±1, write Π_{S} as

Acc(k,k,k) ∏_{(k,j,l)∈S,j,l≠k} Acc(k,j,l) ∏_{(i,k,l)∈S,i,l≠k} Acc(i,k,l) ∏_{(i,j,k)∈S,i,j≠k} Acc(i,j,k)  (3.10)

as the rest of the variables are fixed. The three products of (3.10) can be written as A^{(1)}(f_{k}), A^{(2)}(f′_{k}) and B^{(1)}(g_{k},g′_{k}) respectively, for some Boolean functions A^{(1)}, A^{(2)} and B^{(1)}.

Expanding the definition of Acc(k,k,k) and using x ∧ y = \frac{1+x+y−xy}{2} for A(f′_{k}) ∧ B_{k}(g′_{k}) we see that (3.10) can be written as the sum of four terms of the form

B_{k}(h_{kkk})A′(f_{k})A′′(f′_{k})C(g_{k},g′_{k}) ,  (3.11)

each with a coefficient 1/2, for some Boolean functions A′, A′′and C closely related to A^{(1)}, A^{(2)} and B^{(1)}. To be more precise

A′(f_{k}) = A(f_{k})A^{(1)}(f_{k}) ,
A′′(f′_{k}) = A^{(2)}(f′_{k}) or A′′(f′_{k}) = A(f′_{k})A^{(2)}(f′_{k}) ,

and

C(g_{k},g′_{k}) = B_{k}(g_{k})B^{(1)}(g_{k},g′_{k}) or C(g_{k},g′_{k}) = B_{k}(g_{k})B_{k}(g′_{k})B^{(1)}(g_{k},g′_{k}) .

We want to prove that if the expectation of (3.10)is large then the provers P_{1} and P_{2} in the two prover game can convince the verifier of that protocol to accept with high probability. To this end we use the tables in the given PCP to construct strategies for P_{1} and P_{2}. We need to be slightly careful since not all derived tables can be used by a given prover as it might depend on information not available to this particular prover.

In the present situation the functions A′and A′′depend only on U and the fixations made and hence are available for player P_{2} to design a strategy. B_{k} is the original long code on W_{k} and hence is useful for extracting a strategy for P_{1}. Finally C is a function that depends on both U and W_{k} and as this is not fully known to either P_{1} or P_{2}, C is not useful for designing strategies.

Since we only have one remaining object of each type, let us for readability discard the index replacing f_{k} by f, W_{k} by W, etc.

We now want to compute the expected value of (3.11) over random choices of f, f′, g and g′. Expanding all factors except A′′(f′) by the Fourier transform we get

∑_{α,β,γ,γ′}Â′_{α}B̂_{β}Ĉ_{γ,γ′}E_{f,f′,g,g′} [χ_{α} (f)χ_{β}(gf(f′∧ g′))χ_{γ}(g)χ_{γ′}(g′)A′′(f′)] .  (3.12)

Taking the expectation over f we see, using Lemma 2.3, that any term with α ≠ π_{2}(β) vanishes while if we have equality the expectation is 1. Similarly, considering the expectation over g, we see that only terms with β = γ give a nonzero contribution. Finally, fixing f′and considering expectation over g′, we see that only terms with γ′= β ∩ π^{−1} (f^{′−1}(−1)) remain nonzero.

This implies that (3.12) reduces to

E_{U,W,f′}[ ∑_{β} Â′_{π_{2}(β)}B̂_{β}Ĉ_{β,β∩π^{−1} (f^{′−1}(−1))} A′′(f′)]  (3.13)

and, fixing U and W, let us estimate

E_{f′}[ ∑_{β} Â′_{π_{2}(β)}B̂_{β}Ĉ_{β,β∩π^{−1} (f^{′−1}(−1))} A′′(f′)] .  (3.14)

Towards this end we have

| E_{f′}[Ĉ_{β,β∩π^{−1} (f^{′−1}(−1))} A′′(f′)] | ≤ E_{f′}[|Ĉ_{β,β∩π^{−1} (f^{′−1}(−1))} |] ≤  (3.15)
2^{−|π(β)|} ∑_{α′⊆π(β)} |Ĉ_{β,β∩π^{−1} (α′)} | ≤ 2^{−|π(β)|/2} ( ∑_{α′⊆π(β)} Ĉ_{β,β∩π^{−1} (α′)}^{2} ) ^{1/2}.

Substituting this estimate into (3.14) we get the upper estimate

∑_{β} |Â′_{π_{2}(β)}B̂_{β}|2^{−|π(β)|/2} ( ∑_{α′⊆π(β)} Ĉ_{β,β∩π^{−1} (α′)}^{2} ) ^{1/2}  (3.16)

and applying the Cauchy-Schwarz inequality over β this is bounded by

( ∑_{β} B̂_{β}^{2}Â_{π_{2}(β)}^{′2}2^{−|π(β)|} ) ^{1/2}( ∑_{β,β_{1}} Ĉ_{β,β_{1}}^{2}) ^{1/2} ≤ ( ∑_{β} B̂_{β}^{2}Â_{π_{2}(β)}^{′2}2^{−|π(β)|} ) ^{1/2},  (3.17)

which is our final upper bound for the absolute value of the expectation of Π_{S} when U and W are fixed. As E[X^{2}] ≥ E[X]^{2} we have

E_{U,W}[ ∑_{β} B̂_{β}^{2}Â_{π_{2}(β)}^{′2}2^{−|π(β)|} ] ≥ E_{U,W}[|E_{f,f′,g,g′}[Π_{S}]|^{2}] ≥ E_{U,W}[|E_{f,f′,g,g′}[Π_{S}]|]^{2} ≥ E[Π_{S}]^{2} ≥ T_{S}^{2} .

The rest of the proof now follows along the same lines as end of the proof for the basic test. In that proof we had established that the right hand side of (3.6) was large and used this to derive strategies for the provers. We now have proved that a very similar sum is large. The fact that we have replaced Â_{π_{2}(β)} by Â_{π_{2}(β)}^{′2} is only to our advantage. As A′is a derived table we cannot make sure that it is folded over true and thus when P_{2} picks α with probability Â_{α}^{′2}the set α might be empty. In this case P_{2} might return any assignment and we assume that the verifier rejects in this case. This does not disturb the analysis as B is folded over true and hence |β| is odd which implies that π_{2}(β) is nonempty.

3.2.2 The bipartite graph test

In this section we study the following test.

k-iterated bipartite graph PCP

1. V chooses U as in 2PP(u).

2. V chooses independently k sets (W_{l})_{l=1}^{k}, that can appear with U in 2PP(u). Each W_{l} is chosen with the distribution induced by 2PP(u), i. e., the distribution of the pair U,W_{l} is the same as the distribution of U,W in 2PP(u).

3. V chooses 2k functions (f_{i})_{i=1}^{k} and (f′_{i})_{i=1}^{k} on U uniformly at random.

4. For each l, 1 ≤ l ≤ k, V chooses two functions g_{l} and g′_{l}on W_{l} uniformly at random.

5. For each pair i,l define a function h_{il} by setting for each y ∈ {−1,1}^{W_{l}},

h_{il}(y) = g_{l}(y)f_{i}(π(y))(g′_{l}(y) ∧ f′_{i}(π(y))) .

6. V accepts iff B_{W_{l}}(h_{il}) = B_{W_{l}}(g_{l})A_{U}(f_{i})(B_{W_{l}}(g′_{l}) ∧ A_{U}(f′_{i})) for all 1 ≤ i,l ≤ k.

We have the following theorem.

Theorem 3.4. The bipartite graph test has completeness 1 and soundness 2^{−k^{2}} + d_{c}^{Ω(u)}.

Proof. The completeness is again not difficult and we leave it the reader to verify that indeed V always accepts a correct proof for a correct statement.

In the analysis of the soundness let us use notation similar to the one used in the previous proof, e.g., writing B_{l} instead of B_{W_{l}}and A instead of A_{U}. Also define

Acc(i,l) = B_{l}(h_{il})B_{l}(g_{l})A(f_{i})(A(f′_{i}) ∧ B_{l}(g′_{l})) ,

which is 1 if the test involving h_{il} accepts and −1 if the test fails. Now we want to calculate the expected value of

∏_{(i,l)∈[k]×[k]}\frac{1 + Acc(i,l)}{2} = 2^{−k^{2}} ∑_{S⊆[k]×[k]} ∏_{(i,l)∈S}Acc(i,l) .  (3.18)

Let T_{S} be the expectation of the product for S and the goal is again to, for any nonempty set S, give a prover-strategy with success rate |T_{S}|^{O(1)}. We start by, as already done in [12], reducing to the case of special S and let T_{2d} be the result when S is the edge set of the complete bipartite graph on [2] × [d].

Lemma 3.5 ([12]). For any nonempty S, there is an integer d such that |T_{S}| ≤ |T_{2d}|^{1/2}.

Proof. As all coordinates are treated symmetrically me may, without loss of generality, assume that (1,1) ∈ S and that (1,2),...(1,d) are the other vertices in S connected to 1. Let us divide our random choice of (f_{i},f′_{i},g_{l},g′_{l})_{i,l=1,...,k} into X given by choice of (f_{1},f′_{1}), and Y given by choice of the rest. Let S_{1} be the subset of S given by (1,1),(1,2)...(1,d). Then

E_{X,Y}[ ∏_{(i,l)∈S}Acc(i,l)] = E_{X,Y}[∏_{l=1}^{d} Acc(1,l) · ∏_{(i,l)∈S\S_{1}}Acc(i,l)] =

E_{X,Y}[F (X,Y)G(Y)] = E_{Y}[E_{X}[F (X,Y)]G(Y)]

for some functions F and G with values in {−1,1}. Now applying the Cauchy-Schwarz inequality this can be bounded by

\begin{matrix}√ & \overline{E_{Y}[(E_{X}[F (X,Y)])^{2}]} \\ √ & \overline{E_{Y}[G(Y)^{2}]} \end{matrix} ≤ \sqrt{E_{Y}[(E_{X}[F (X,Y)])^{2}]} =
\sqrt{E_{Y}[E_{X_{1}}[F (X_{1},Y)] · E_{X_{2}}[F (X_{2},Y)]]} = \sqrt{E_{X_{1},X_{2},Y}[F (X_{1},Y) · F (X_{2},Y)]}

where X_{1},X_{2} are identically distributed as X and are independent. The proof is completed by the observation that F (X_{1},Y) · F (X_{2},Y) is equal to ∏ _{l=1}^{d} Acc(1,l) · ∏ _{l=1}^{d} Acc(2,l), which is exactly the same as T_{S′}where S′is a complete bipartite graph on [2] × [d].

Thus it is sufficient to find a good strategy based on |T_{2d}| being large. Using the definition of Acc and canceling the factors B_{l}(g_{l}) that appears exactly twice, we have

T_{2d} = E [ ∏_{l=1}^{d} B_{l}(h_{1l})B_{l}(h_{2l})A(f_{1})A(f_{2})(A(f′_{1})A(f′_{2}) ∧ B_{l}(g′_{l}))] .  (3.19)

The function g_{l} affects T_{2d} only through h_{1l} and h_{2l} and replacing B_{l}(h_{1l}) and B_{l}(h_{2l}) by their Fourier expansions we see that

E_{g_{l}}[B_{l}(h_{1l})B_{l}(h_{2l})] = ∑_{β_{1},β_{2}} B̂_{l,β_{1}}B̂_{l,β_{2}}E_{g_{l}}[χ_{β_{1}}(g_{l}f_{1}(g′_{l}∧ f′_{1}))χ_{β_{2}}(g_{l}f_{2}(g′_{l}∧ f′_{2}))] =
∑_{β} B̂_{l,β}^{2}χ_{β}(f_{1}f_{2})χ_{β}(f′_{1}f′_{2}∧ g′_{l}) .  (3.20)

Substituting this into (3.19) we get

E [ ∏_{l=1}^{d} ( ∑_{β_{l}} B̂_{l,β_{l}}^{2}χ_{β_{l}}(f_{1}f_{2})χ_{β_{l}}(f′_{1}f′_{2}∧ g′_{l})) A(f_{1})A(f_{2})((A(f′_{1})A(f′_{2})) ∧ B_{l}(g′_{l}))] .  (3.21)

Let us now consider the expectation over f_{1} and f_{2}. If d is even then the dependence of (3.21) on f_{1} and f_{2} is of the form

∏_{l=1}^{d} χ_{β_{l}}(f_{1}f_{2}) .

which has expected value 0 unless ⊕_{j}π_{2}(β_{l}) = ∅ while the expectation is 1 if we have equality. If d is odd, then the dependence of f_{1} and f_{2} is of the form

A(f_{1})A(f_{2})∏_{l=1}^{d} χ_{β_{l}}(f_{1}f_{2}) .

Replacing A(f_{1}) and A(f_{2}) by their Fourier expansions we see that the expectation of this with respect to f_{1} and f_{2} equals Â_{α}^{2} where

α = ⊕_{l}π_{2}(β_{l}) .

Now let us turn to analyzing the rest of (3.21). First note that

∏_{l=1}^{d} (A(f′_{1})A(f′_{2}) ∧ B_{l}(g′_{l})) = (A(f′_{1})A(f′_{2}) ∧ ∏_{l=1}^{d} B_{l}(g′_{l})) .

We have (x ∧y) = \frac{1+x+y−xy}{2} and we are now ready to consider the expectation over f′_{1}and f′_{2}and g′_{l}. We have expressions of the form

(A(f′_{1})A(f′_{2}))^{a} ∏_{j=l}^{d} χ_{β_{l}}(f′_{1}f′_{2}∧ g′_{l})(∏_{l=1}^{d} B_{l}(g′_{l}))^{b} ,  (3.22)

for a,b ∈ {0,1}. Now, view

C(g′_{1},g′_{2}...g′_{d}) = (∏_{l=1}^{d} B_{l}(g′_{l}))^{b}

as a Boolean function with Fourier coefficients Ĉ_{γ_{1},γ_{2},....γ_{d}}, and thus (3.22) equals

∑_{γ_{1},γ_{2},...γ_{l}}(A(f′_{1})A(f′_{2}))^{a}Ĉ_{γ_{1},γ_{2},....γ_{d}}∏_{j=l}^{d} χ_{β_{l}}(f′_{1}f′_{2}∧ g′_{l})χ_{γ_{l}}(g′_{l}) .  (3.23)

Let α′= ∪_{l=1}^{d} π(β_{l}). For a fixed choice of f′_{1}f′_{2}= f′we get a nonzero expected value over (g′_{l})_{l=1}^{d} iff

γ_{l} = β_{l} ∩ π^{−1} (f^{′−1}(−1)) for all l, giving a unique non-zero term. Defining γ_{l}^{β⃗,f′} to be this value we get

|E_{f′_{1},f′_{2},g′_{1},g′_{2},...g′_{d}} [(A(f′_{1})A(f′_{2}))^{a} ∏_{j=l}^{d} χ_{β_{l}}(f′_{1}f′_{2}∧ g′_{l})(∏_{l=1}^{d} B_{l}(g′_{l}))^{b}] | ≤  (3.24)

|E_{f′_{1},f′_{2}} \left[{ \atop Ĉ_{γ_{1}^{β⃗,f′},γ_{2}^{β⃗,f′},....γ_{d}^{β⃗,f′}}}\right] | ≤ 2^{−|α′|/2} ,  (3.25)

where the last inequality follows from the Cauchy-Schwarz inequality using a similar calculation to that in (3.5). This means that in the case when d is even we get the upper estimate

∑_{⊕_{l}π_{2}(β_{l})=∅} ∏_{l=1}^{d} B̂_{l,β_{l}}^{2}2^{−|α′|/2}  (3.26)

for |T_{2d}| while in the case when d is odd we get

∑ Â_{⊕_{l}π_{2}(β_{l})}^{2} ∏_{l=1}^{d} B̂_{l,β_{l}}^{2}2^{−|α′|/2} ,  (3.27)

where in both cases we have α′= ∪_{l=1}^{d} π(β_{l}).

Strategies for the provers can now be defined as follows. P_{1} upon receiving W, picks β with probability B̂_{β}^{2} and returns a random y ∈ β. P_{2} upon receiving U picks d − 1 random W_{l}, l = 2...d and picks β_{2},...β_{d} with probability ∏ _{l=2}^{d} B̂_{l,β_{l}}^{2} and computes α′′= ⊕_{l=2}^{d} π_{2}(β_{l}). If d is even P_{2} returns a random x ∈ α′′. If d is odd P_{2} also picks α with probability Â_{α}^{2} and returns a random element in α′′⊕ α. Note that by folding, in both cases the defined set is of odd cardinality and hence is not empty.

The probability of success is, in the case of even d, at least

∑_{⊕_{l}π_{2}(β_{l})=∅} ∏_{l=1}^{d} B̂_{l,β_{l}}^{2}(∑ |β_{l}|)^{−1}  (3.28)

and in the case of odd d it as at least

∑ Â_{⊕_{l}π_{2}(β_{l})}^{2} ∏_{l=1}^{d} B̂_{l,β_{l}}^{2}(∑ |β_{l}|)^{−1} .  (3.29)

Using (3.7) these probabilities can be related to expressions (3.26) and (3.27) in a way similar to the basic proof case. We omit the details. The result is that the verifier in 2PP(u) accepts with probability |T_{2d}|^{O(1)} and the theorem follows.

3.2.3 Adaptive tests

In this section we prove Theorem 1.4 by defining a suitable adaptive test. The theorem then follows from analyzing the completeness, which is done in Lemma 3.6 and the soundness which is done in Lemma 3.7 Guruswami et al. [7] give an adaptive test reading three bits that has perfect completeness and soundness \frac{1}{2} + ϵ for any ϵ > 0. The non-adaptive version of this test has the same parameters except that it reads 4 bits. The natural iterated test based on this test reads 2k + k^{2} bits in the adaptive setting and 2k + 2k^{2} bits in the non-adaptive setting. It has perfect completeness and it turns out that soundness is essentially 2^{−k^{2}} also for this test.

Thus its parameters, when adaptive, are the same as those of the test of Samorodnitsky and Trevisan while achieving perfect completeness. As sketched in [8], this test can be designed and analyzed with the same basic two-prover protocol as the previous tests but the construction turns out to be technically simpler if we modify the two-prover protocol. We do this to obtain the property called “smoothness” in [10]. We need that for two different answers by P_{1}, with high probability the answers by P_{2} causing acceptance are also different. This is achieved by sending a large number of identical clauses to both provers.

u-parallel two-prover protocol with redundancy factor T, 2PPe( u,T )

1. V chooses T u clauses (C_{k_{i}})_{i=1}^{T u} uniformly at random. Then he randomly selects u clauses (C_{j_{i}})_{i=1}^{u} out of these T u clauses and randomly selects a variable x_{j_{i}} from each clauses C_{j_{i}}. He sends (k_{i})_{i=1}^{T u} to prover P_{1}; and to prover P_{2}, he sends the u chosen variables (x_{j_{i}})_{i=1}^{u} together with the (T − 1)u clauses not selected.

2. V receives values for the u chosen variables (x_{j_{i}})_{i=1}^{u} from P_{2} as well as 3(T − 1)u values for the variables in the clauses sent to P_{2}. V also receives 3T u values from P_{1} to the variables in the clauses sent to P_{1}. V accepts if no two values are inconsistent and all the picked clauses are satisfied.

We again call the sets of variables sent to the two provers U and W, respectively. Note that this time U is of size u(3T − 2) and W is of size 3uT while as before we have U ⊂ W. Note also that for each fixed set of (T − 1)u clauses sent to both players, we have an instance of the 2PP(u). This implies that the soundness of 2PPe(u,T) is at most that of 2PP(u) and in particular it is upper bounded by d_{c}^{u}.

We now describe the PCP. It depends on the parameters u and T but has also additional parameters k and ϵ. For notational convenience we suppress the former.

k-iterated non-adaptive PCP of bias ϵ

1. V chooses U as in 2PPe(u,T).

2. V chooses independently k sets (W_{j})_{j=1}^{k} , that can appear with U in 2PPe(u,T). Each W_{j} is chosen with the distribution induced by 2PPe(u,T), i. e., the distribution of the pair U,W_{j} is the same as the distribution of U,W in 2PPe(u,T).

3. V chooses k functions (f_{i})_{i=1}^{k} on U uniformly at random and reads the bits A_{U}(f_{i}).

4. For each j, 1 ≤ j ≤ k, V chooses a function g_{j} on W_{j} uniformly at random and reads the bits B_{W_{j}}(g_{j}).

5. For each pair i,j define a function h_{ij} by setting, independently, for each y ∈ {−1,1}^{W_{j}}, h_{ij}(y) = −1 with probability 1 − ϵ and otherwise h_{ij}(y) = 1.

6. For each pair i,j, if A(f_{i}) = 1, V checks that B_{j}(g_{j}(f_{i} ∧ h_{ij})) = B_{j}(g_{j}) and otherwise V checks that B_{j}(g_{j}(−f_{i}∧ h_{ij})) = B_{j}(g_{j}).

7. V accepts if all tests accept.

Completeness is straightforward.

Lemma 3.6. The adaptive k-iterated test with bias ϵ, accepts with probability 1, i. e, it has perfect completeness.

Proof. Fix an i and a j. Suppose that we have a correct proof of a correct statement based on the global assignment z. If A(f_{i}) = 1 then f_{i}(π^{U}(z)) = 1 and we have

B_{j}(g_{j}(f_{i}∧ h_{ij})) = g_{j}(π^{W}(z))(f_{i}(π^{U}(z)) ∧ h_{ij}(π^{W}(z))) = g_{j}(π^{W}(z)) = B_{j}(g_{j}) .

The case A(f_{i}) = −1 is similar.

We next turn to soundness.

Lemma 3.7. Suppose that T ≥ ϵ^{−5} and we are given a proof that makes the verifier in the adaptive iterated test with parameter ϵ accept with probability 2^{−k^{2}} + 2δ where δ > 6ϵ. Then we can find strategies for P_{1} and P_{2} in 2PPe(u,T) that makes the verifier of that protocol accept with probability at least ϵ^{2}(δ − 6ϵ)^{2}/2.

Proof. The proof follows along the same lines as the result for the protocol with k = 1 given in [7] which in turn is based on the proof that 3SAT is inapproximable for satisfiable instances in [14].

Let

Acc(i,j) = \frac{1}{2} ((1 + A(f_{i}))B_{j}(g_{j})B_{j}(g_{j}(f_{i}∧ h_{ij})) + (1 − A(f_{i}))B_{j}(g_{j})B_{j}(g_{j}(−f_{i}∧ h_{ij}))) ,

which is 1 if the test given by (i,j) accepts and −1 otherwise. We have an expansion like (3.18) and by the assumption of the lemma implies that we have a nonempty S such that

E [ ∏_{(i,j)∈S} Acc(i,j)] ≥ 2δ .  (3.30)

As all coordinates are symmetric we may assume that (1,1) ∈ S. Now fix the values of g_{j} and f_{i} for i,j ≥ 2 and h_{ij} for (i,j) ≠ (1,1) to any constants without decreasing the expected value obtaining

E_{U,W_{1},f_{1},g_{1},h_{11}}[Acc(1,1)A^{(1)}(f_{1})B^{(1)}(g_{1})] ≥ 2δ  (3.31)

for some Boolean functions A^{(1)} and B^{(1)}. Using the expression for Acc(1,1) we get an expression of the form

A′(f_{1})B(g_{1}(f_{1}∧ h_{11}))C(g_{1})  (3.32)

or

A′(f_{1})B(g_{1}(−f_{1}∧ h_{11}))C(g_{1})  (3.33)

whose expectation over the choice of U, f_{1}, W_{1}, g_{1} and h_{11} is at least δ. Here A′, B and C are Boolean functions where B is the original B_{1} and A′is a function only depending on U. Since f is chosen with the same distribution as −f we might as well study (3.32) and let us drop the subscripts for readability. Replacing each function by its Fourier expansion, we get that the expectation of (3.32) equals

E_{U,W,f,g,h}[ ∑_{α,β,γ} Â′_{α}B̂_{β}Ĉ_{γ}χ_{α} (f)χ_{β}(g(f ∧ h))χ_{γ}(g)] .  (3.34)

Taking expectation over g we see that terms with β ≠ γ have expectation 0 and thus (3.34) equals

E_{U,W}[ ∑_{α,β} Â′_{α}B̂_{β}Ĉ_{β}E_{f,h} [χ_{α} (f)χ_{β}((f ∧ h))] ] .  (3.35)

If α ⊈ π(β) the expectation over f yields 0 and thus we need to study

E_{f,h}[χ_{α} (f)χ_{β}(f ∧ h)]  (3.36)

where α ⊆ π(β). Using the definition of the characters (3.36) equals

E_{f,h} [ ∏_{x∈α} ( f(x) ∏_{y∈β∩π^{−1} (x)}(f(x) ∧ h(y))) ∏_{x∈π(β)\α} ( ∏_{y∈β∩π^{−1} (x)}(f(x) ∧ h(y))) ]  (3.37)

and as the different x behave independently we can analyze each factor independently. We have f(x) = 1 with probability 1/2 and in this case

∏_{y∈β∩π^{−1} (x)} (f(x) ∧ h(y))) = 1 ,

while while if f(x) = −1, it has expectation over h that equals (2ϵ − 1)^{s_{x}} where s_{x} = |π^{−1} (x) ∩ β|. We conclude that the expectation of (3.37) equals

∏_{x∈α∩π(β)} (\frac{1}{2}(1 − (2ϵ − 1)^{s_{x}})) ∏_{x∈π(β)\α} (\frac{1}{2}(1 + (2ϵ − 1)^{s_{x}})) ,

and defining this expression to be p(α,β), we conclude that (3.35) equals

E_{U,W}[ ∑_{β,α⊆π(β)} Â′_{α}B̂_{β}Ĉ_{β}p(α,β)] .  (3.38)

By assumption this expectation is at least δ and we need to design strategies for P_{1} and P_{2}.

The strategies of the two provers are the standard strategies. i. e., P_{2} chooses an α with probability Â_{α}^{′2}and returns a random x ∈ α. Similarly P_{1} chooses a random β with probability B̂_{β}^{2} and returns a random y ∈ β. Again A′cannot be assumed to be folded as it is a derived table. If α is the empty set we do not care what P_{2} does and we assume in the analysis that the verifier rejects. The table B, on the other hand, is the original table and hence β is nonempty and any y ∈ β satisfies the selected clauses. We conclude that the strategy of the provers is successful with probability at least

E_{U,W}[ ∑_{β,∅≠α⊆π(β)} Â_{α}^{′2}B̂_{β}^{2}|β|^{−1} ] .  (3.39)

We need to prove that this is large based on (3.38) being at least δ.

First note that

∑_{β} |B̂_{β}Ĉ_{β}| ≤ ( ∑_{β} B̂_{β}^{2}) ^{1/2}( ∑_{β} Ĉ_{β}^{2}) ^{1/2} ≤ 1 ,  (3.40)

and the quantity that multiplies B̂_{β}Ĉ_{β} in (3.38) satisfies

| ∑_{α⊆π(β)} Â′_{α}p(α,β)| ≤ ( ∑_{α⊆π(β)} Â_{α}^{′2}) ^{1/2}( ∑_{α⊆π(β)} p^{2}(α,β)) ^{1/2}

≤ ( ∑_{α⊆π(β)} p^{2}(α,β)) ^{1/2} ≤ (1 − ϵ)^{|π(β)|/2} .  (3.41)

To see the last inequality in (3.41) note that the sum equals

∏_{x∈π(β)} ( ( \frac{1}{2}(1 − (2ϵ − 1)^{s_{x}})) ^{2}+ ( \frac{1}{2}(1 + (2ϵ − 1)^{s_{x}})) ^{2}) .  (3.42)

The factor corresponding to x in (3.42)is of the form a^{2}+b^{2} where |a|+|b| = 1 and max(|a|,|b|) ≤ 1−ϵ, and hence it is bounded by (1 − ϵ) and this gives the bound.

Our redesigned two-prover protocol enables us to control the size of projections nicely.

Lemma 3.8. For any fixed W and β we have

Pr_{U}[|π(β)| < |β|] < \frac{|β|^{2}}{2T} .  (3.43)

Proof. For the event in (3.43) to happen there must be two different elements of β that project to the same element. There are at most |β|^{2}/2 pairs and the probability that any pair project to the same element is at most 1/T. This follows since two different elements differ in at least one coordinate and the probability that a given coordinate does not appear in U is bounded above by 1/T. The lemma follows from the union bound.

Let us return to (3.38) and consider the terms corresponding to a fixed β. If |β| ≥ 2ϵ^{−2} then using Lemma 3.8, we see, as T ≥ ϵ^{−5} , that except with probability 2ϵ we have |π(β)| ≥ 2ϵ^{−2} in which case (3.41) is bounded by

(1 − ϵ)^{ϵ^{−2}} ≤ e^{ϵ^{−1}} ≤ ϵ .

We conclude that

E_{U,W}[ ∑_{|β|≥2ϵ^{−2} ,α⊆π(β)} Â′_{α}B̂_{β}Ĉ_{β}p(α,β)] ≤ E_{U,W}[ ∑_{|β|≥2ϵ^{−2}} B̂_{β}Ĉ_{β}(Pr[|π(β)| ≤ 2ϵ^{−1} ] + ϵ)] ≤ 3ϵ. (3.44)

It follows that

E_{U,W}[ ∑_{|β|≤2ϵ^{−2} ,α⊆π(β)} Â′_{α}B̂_{β}Ĉ_{β}p(α,β)] ≥ δ − 3ϵ ,  (3.45)

and we want to bound the contribution from α = ∅. Note that if |β| ≤ 2ϵ^{−2} then, by Lemma 3.8, except with probability 2ϵ each s_{x} is one. In this case

p(∅,β) = ϵ^{|β|} ≤ ϵ

and we conclude that the total expectation of terms containing α = ∅ is at most 3ϵ and hence we have

E_{U,W}[ ∑_{|β|≤2ϵ^{−2} ,∅≠α⊆π(β)} Â′_{α}B̂_{β}Ĉ_{β}p(α,β)] ≥ δ − 6ϵ .  (3.46)

Returning to (3.39) we see that the provers are successful with with probability at least

\frac{ϵ^{2}}{2}E_{U,W}[ ∑_{β,∅≠α⊆π(β),|β|≤2ϵ^{−2}}  Â_{α}^{′2}B̂_{β}^{2}] .

Now by the above reasoning we have the following chain of equalities, where all sums are over the set

{β,∅ ≠ α ⊆ π(β),|β| ≤ 2ϵ^{−2} } :

(δ − 6ϵ)^{2} ≤ (E_{U,W}[∑ Â′_{α}B̂_{β}Ĉ_{β}p(α,β)] )^{2} ≤ E_{U,W}[(∑ Â′_{α}B̂_{β}Ĉ_{β}p(α,β)) ^{2}] ≤
E_{U,W}[( ∑ Â_{α}^{′2}B̂_{β}^{2}) ( ∑ Ĉ_{β}^{2}p^{2}(α,β)) ] ≤ E_{U,W}[∑ Â_{α}^{′2}B̂_{β}^{2}] ,

where the last inequality follows from

∑_{β} ∑_{α⊆β} Ĉ_{β}^{2}p^{2}(α,β) ≤ ∑_{β} Ĉ_{β}^{2} ≤ 1 ,

where we again used the last inequality of (3.41). We conclude that the verifier in the two-prover protocol accepts with the given strategies with probability at least ϵ^{2}(δ − 6ϵ)^{2}/2 and the proof is complete.

4 The case of larger domains

In this section we prove Theorem 1.5. This is done by a natural extension of the protocols from the previous sections. Before we present our protocols we give some definitions and recall some background results.

4.1 Background in the large domain case

Let ℤ_{p} denote the multiplicative group given by the p^{th} roots of unity. Let ζ = e^{2πi/p} be the basic p^{th} root of unity. To generalize the Boolean ∧ we define an operation mult( , ) as:

mult(ζ^{i},ζ^{j}) = ζ^{ij} .

We have the following useful lemma Lemma 4.1. If x and y are p^{th}roots of unity, we have

mult(x,y) = \frac{1}{p} ∑_{i=0}^{p−1} ∑_{j=0}^{p−1} x^{i}y^{j}ζ^{−ij} .

Proof. Suppose y = ζ^{i_{0}}. Fix i and consider the inner sum. For i ≠ i_{0} the value is 0 while for i = i_{0} it is p. This implies that the total sum equals x^{i_{0}} which is in fact mult(x,y).

We define long p codes as the natural extension of the long code. Positions are indexed by functions f : {−1,1}^{t} → ℤ_{p} and in the code for x this position takes value f(x).

Let A be a table containing a value A(f) ∈ ℤ_{p} for every function f : {−1,1}^{t} → ℤ_{p}. We make the following definitions for such a table.

Definition 4.2. A table A is folded over true if A(ζ^{a}f) = ζ^{a}A(f), for 0 ≤ a ≤ p − 1 and all f.

Definition 4.3. A table A respects exponentiation if A(f^{a}) = A(f)^{a} for 0 ≤ a ≤ p − 1 and all f.

Definition 4.4. A table A is conditioned upon a function h: {−1,1}^{t} → {1,ζ} (1 represents false and ζ represents true), if A(f) = A(mult(f,h)) for all f.

Now we briefly explain Fourier analysis of long p-codes. For every function α : {−1,1}^{t}→ GF (p), where GF (p) is represented by {0,1,...p − 1}, there is a character χ_{α} defined as

χ_{α} (f) = ∏_{x∈{−1,1}^{t}} f(x)^{α(x)} .

Note that α is a “function” rather than a “set” as in binary case and that the transform takes complex values. We denote by N(α) the set on which α takes nonzero values i. e.,

N(α) = {x|α(x) ≠ 0} .

Every table A can be written as A(f) = ∑_{α} Â_{α}χ_{α} (f) with ∑_{α} |Â_{α}|^{2} = 1. We can assume that tables are folded or conditioned upon a given function by using appropriate access mechanisms. Following are easy consequences of folding and conditioning.

Lemma 4.5. If A is folded over true and Â_{α} ≠ 0, then ∑_{x∈{−1,1}^{t}} α(x) = 1 modp. In particular N(α) is a nonempty set.

Lemma 4.6. If A is conditioned upon a function h : {−1,1}^{t} → {1,ζ} and Â_{α} ≠ 0, then for every x ∈ N(α), h(x) is true, i. e., h(x) = ζ.

In this section our numbers are elements of the number field ℚ(ζ), the rational numbers with the p^{th} root of unity added. We use the homomorphism σ_{a}, 0 ≤ a ≤ p − 1 which has the property that σ_{a}(ζ^{i}) = ζ^{ia}. For x a p^{th}root of unity we have σ_{a}(x) = x^{a} but this is not true in general.

We have the following straightforward lemma of which we omit the proof.

Lemma 4.7. For x ≠ 1 a p^{th}root of unity we have

∑_{a=0}^{p−1} σ_{a}(x) = 0 .

Finally define

π_{p}(β)(x) = ∑_{y∈π^{−1} (x)}β(y) modp

as the generalization of π_{2}. Lemma 2.8 generalizes.

Lemma 4.8. Let β ⊆ {−1,1}^{W}, U ⊆ W and f : {−1,1}^{U} → ℤ_{p}. Then

χ_{β}(f) = χ_{π_{p}(β)}(f) .

4.2 The basic test

We first define the basic test which is completely analogous to the binary case. We assume that tables A,B are folded over true and respect exponentiation. The table B (supposed long p-code on W) is conditioned upon the CNF formula φ_{W}.

Basic mod-p PCP

1. V chooses U, W and φ_{W} as in 2PP(u).

2. V chooses two functions f and f′on U, taking values in ℤ_{p} uniformly at random.

3. V chooses two random functions g and g′on W taking values in ℤ_{p} uniformly at random. V defines a third function h by setting for each y ∈ {−1,1}^{W}, h(y) = g(y)f(π(y)) mult(g′(y),f′(π(y))).

4. V accepts iff B(h) = B(g)A(f) mult(B(g′),A(f′)).

Obviously the completeness of the basic test is 1 and we turn to the soundness.

Lemma 4.9. If the verifier in the basic test accepts with probability (1+δ)/p then there exists a strategy for P_{1} and P_{2} in 2PP(u) that makes the verifier accept with probability p^{−O(1)} δ^{O(1)}.

First note that

B(h)^{−1} B(g)A(f) mult(B(g′),A(f′))

is a p^{th}root of unity which is 1 iff the test accepts.

This implies, under the hypothesis of the lemma and using Lemma 4.7, that

E_{U,W,f,f′,g,g′}[∑_{a=1}^{p−1} σ_{a}(B(h)^{−1} B(g)A(f) mult(B(g′),A(f′)))] = δ .

Using Lemma 4.1 and the fact that our tables respect exponentiation we see that

E_{U,W,f,f′,g,g′}[∑_{b=0}^{p−1} ∑_{c=0}^{p−1} ∑_{a=1}^{p−1} B(h)^{−a} B(g^{a})A(f^{a})B(g^{′ab})A(f^{′ac})ζ^{−bc}] = pδ .

We conclude that there must be some value of (a,b,c) such that

|E_{U,W,f,f′,g,g′}[B(h)^{−a} B(g^{a})A(f^{a})B(g^{′ab}),A(f^{′ac})]| ≥ p^{−2} δ .  (4.1)

Replacing (h,g,f,g′,f′) by (h^{a},g^{a},f^{a},g^{′a},f^{′)}preserves probability and hence changing the value of c, we can without loss of generality assume that a = 1.

Fix U,W,f′and g′and let us study

E_{f,g}[B(h^{−1} )B(g)A(f)] .  (4.2)

Replacing each function by its Fourier expansion we see that this equals

∑_{β_{1},β_{2},α} B̂_{β_{1}}B̂_{β_{2}}Â_{α}E_{f,g}[χ_{β_{1}}(f^{−1} g^{−1} mult(f′,g′)^{−1} )χ_{β_{2}}(g)χ_{α} (f)] .

The inner expected value is 0 unless β_{1} = β_{2} and π_{p}(β_{1}) = α and hence (4.2) equals

∑_{β} B̂_{β}^{2}Â_{π_{p}(β)}χ_{β}(mult(f′,g′)^{−1} ) .  (4.3)

Returning to (4.1) we need to analyze

E_{f′,g′}[χ_{β}(mult(f′,g′)^{−1} )B(g^{′b})A(f^{′c})] .  (4.4)

Fix the value of f′. When b = 0, averaging over g′gives 0 unless f′(π(z)) = 1 for all z ∈ N(β). The probability of picking such an f′is p^{−|π(N(β))|}. Now consider the case when b ≠ 0. Define β′as follows: for every y, β′(y) = b^{−1} e(y)β(y) where f′(π(y)) = ζ^{e(y)}. Averaging (4.4) over g′yields B̂_{β′}A(f^{′c}).

We note that f′s which are different on π(N(β)) give different β′. Let Δ_{β} be the set of all possible β′. We have |Δ_{β}| = p^{|π(N(β))|} and over all the choices of f′, every β′∈ Δ_{β} occurs equally often. Using this observation and applying the Cauchy-Schwarz inequality gives

| E_{f′}[B̂_{β′}A(f^{′c})] | ≤ E_{f′}[|B̂_{β′}|] = p^{−|π(N(β))|} ∑_{β′∈Δ_{β}} |B̂_{β′}| ≤

p^{−|π(N(β))|/2} ( ∑_{β′∈Δ_{β}} |B̂_{β′}|^{2}) ^{1/2} ≤ p^{−|π(N(β))|/2} .

This implies that we get an overall upper bound on the expectation of (4.1) as

E_{U,W}[ ∑_{β} |B̂_{β}|^{2} |Â_{π_{p}(β)}| p^{−|π(N(β))|/2} ] .

Now we can extract prover strategies in a similar way as in the proof of Lemma 3.2, making use of (3.7). A minor difference is that now α ( β ) are functions and not sets. The provers pick α ( β ) with probability Â_{α}^{2} ( B̂_{β}^{2} ) and pick a random x ∈ N(α) (a random y ∈ N(β) ).

4.2.1 Iterated tests

The basic test in the previous section can be iterated in a way similar to the Section 3.2. We have only attempted the simpler analysis of almost disjoint sets and this is what we present here.

4.2.2 The almost disjoint sets test

We first define the test which is an iteration of the basic test studied in the last section.

k-iterated mod-p almost disjoint sets PCP

1. V chooses U as in 2PP(u).

2. V chooses independently k sets (W_{l})_{l=1}^{k}, that can appear with U in 2PP(u). Each W_{l} is chosen with the distribution induced by 2PP(u), i. e., the distribution of the pair U,W_{l} is the same as the distribution of U,W in 2PP(u).

3. V chooses 2k functions (f_{i})_{i=1}^{k} and (f′_{j})_{j=1}^{k} on U taking values in ℤ_{p} uniformly at random.

4. For each l, 1 ≤ l ≤ k, V chooses two functions g_{l} and g′_{l} on W_{l} taking values in ℤ_{p} uniformly at random.

5. For each triple i,j,l such that i + j + l ≡ 0 modk define a function h_{ijl} by setting for each y ∈ {−1,1}^{W_{l}}, h_{ijl}(y) = g_{l}(y)f_{i}(π(y))mult(g′_{l}(y),f′_{j}(π(y))).

6. V accepts iff B_{W_{l}}(h_{ijl}) = B_{W_{l}}(g_{l})A_{U}(f_{i})mult(B_{W_{l}}(g′_{l}),A_{U}(f′_{j})) for all i + j + l ≡ 0 modk.

We have the following theorem.

Theorem 4.10. The almost disjoint sets test in ℤ_{p} has completeness 1 and soundness p^{−k^{2}} +p^{O(1)}d_{c}^{Ω(u)}, where d_{c} is the constant from Theorem 2.1.

Proof. The completeness is obvious and we need to analyze the soundness. To this end let

Acc(i,j,l) = B_{l}(h_{ijl})^{−1} B_{l}(g_{l})A(f_{i}) mult(A(f′_{j}),B_{l}(g′_{l})) ,

which is 1 if the test associated with (i,j,l) accepts and otherwise it is a different p^{th}root of unity.

Let Z_{0} be the set of all triples (i,j,l) with i + j + l ≡ 0( mod k) and let S ∈ GF (p)^{k^{2}} be a vector whose coordinates are indexed by the triples in Z_{0}. We have

∏_{(i,j,l)∈Z_{0}} \frac{∑ _{a=0}^{p−1} (Acc(i,j,l))^{a}}{p} = p^{−k^{2}} ∑_{S∈GF (p)^{k^{2}}} ∏_{(i,j,l)∈Z_{0}} (Acc(i,j,l))^{S(i,j,l)} .

By Lemma 4.7 this expression equals 1 if the test accepts and is 0 otherwise and thus its expected value is the probability that the test accepts. The term with S ≡ 0 is 1 and to establish the theorem it is sufficient to establish that any term with S ≢ 0 is upper bounded above by p^{O(1)}d_{c}^{Ω(u)}. Let T_{S} be the expected value of the term corresponding to S. We go on to establish a strategy for P_{1} and P_{2} which makes the verifier in 2PP(u) accept with probability p^{−O(1)} |T_{S}|^{O(1)}.

Suppose without loss of generality that S(k,k,k) = r ≠ 0 and fix the values of f_{i}, i ≠ k, f_{j}, j ≠ k and (W_{l},g_{l},g′_{l}) for l ≠ k in such a way as not to decrease |T_{S}|. Since we only have one remaining function of each type let us for readability discard the index.

By Lemma 4.1 and from the fact that any other triple intersects with the given triple in at most one place we conclude that T_{S}, after the above fixings, can be written as the sum of p^{2} terms of the form

B(h)^{−r} A′(f)A′′(f′)C(g,g′) ,  (4.5)

each with a coefficient of complex absolute value 1/p. Here A′, A′′, B, and C takes values which are p^{th} roots of unity. We conclude that there is such an expression of the form (4.5) whose expectation over U,W,h,f,f′,g, and g′is at least |T_{S}|/p.

Here A′and A′′are functions that only depend on U and hence might be used to extract strategy for P_{2}. B is the original long p-code on W = W_{k} and hence is useful for extracting strategy for P_{1}.

We now want to compute the expected value of this expression over random choices of f, f′, g and g′. Expanding all factors except A′′(f′) by the Fourier transform we get

∑_{α,β,γ,γ′}Â′_{α}B̂_{β}Ĉ_{γ,γ′}E[χ_{α} (f)χ_{−rβ} (gf mult(f′,g′))χ_{γ}(g)χ_{γ′}(g′)A′′(f′)] .  (4.6)

Now taking the expected value over f we see that unless α = rπ_{p}(β) the term is 0. Similarly we need γ = rβ. Fix f′and define β′as follows: for every y, β′(y) = re(y)β(y) where f′(π(y)) = ζ^{e(y)}. With this definition, we have

χ_{−rβ} (mult(f′,g′)) = χ_{−β′} (g′) .

Thus unless γ′= β′, the expectation is 0. Thus (4.6) equals

∑_{β} Â′_{rπ_{p}(β)} B̂_{β}Ĉ_{β,β′}A′′(f′) .  (4.7)

Note that β′is uniquely determined by β and f′and functions f′which are different on π(N(β)) give different β′s. Let Δ_{β} be the set of all possible β′s. We have |Δ_{β}| = p^{|π(N(β))|} and over all the choices of f′, every β′∈ Δ_{β} occurs equally often. This implies that

| E_{f′}[Ĉ_{β,β′(β,f′)}A′′(f′)] | ≤ E_{f′}[|Ĉ_{β,β′(β,f′)}|] ≤  (4.8)
p^{−|π(N(β))|} ∑_{β′∈Δ_{β}} |Ĉ_{β,β′}| ≤ p^{−|π(N(β))|/2} ( ∑_{β′∈Δ_{β}} |Ĉ_{β,β′}|^{2})^{1/2} .

Substituting this estimate into (4.7) and using the Cauchy-Schwarz inequality over β we get the upper estimate

( ∑_{β} |B̂_{β}|^{2}|Â′_{rπ_{p}(β)}|^{2}p^{−|π(N(β))|} ) ^{1/2} ( ∑_{β,β′∈Δ_{β}} |Ĉ_{β,β′}|^{2}) ^{1/2} ≤ ( ∑_{β} |B̂_{β}|^{2}|Â′_{rπ_{p}(β)}|^{2}p^{−|π(N(β))|} ) ^{1/2}

for |T_{S}|/p. The same strategy as defined in the basic test now makes the verifier accept in 2PP(u) with probability p^{−O(1)} |T_{S}|^{O(1)} and the theorem follows.

5 Conclusions

We have established that the query efficient test of Samorodnitsky and Trevisan can be extended to include perfect completeness in several different ways. The tests are simple and the analyses are only moderately complicated, in particular the proofs using the approach of [15] are fairly straightforward.

All this taken together gives us good hope that, in the not too distant future, we will see more powerful PCPs with even more applications to inapproximability of NP-hard optimization problems. In particular the fact that we can include perfect completeness gives hope that stronger lower bounds for coloring of graphs of small chromatic number could be possible. Clearly, to obtain such results, obstacles of other nature need also be overcome. We note that some progress for constant colorable graphs has already occurred [9], but getting strong results for 3-colorable graphs seems to require new ideas.

6 Acknowledgments

We would like to thank Sanjeev Arora for several helpful discussions. We are also grateful to the anonymous referees for many comments that helped to improve the quality of the paper.

References

[1] * S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy: Proof verification and the hardness of approximation problems. Journal of the ACM, 45:501–555, 1998. [JACM:10.1145/278298.278306]. 1, 2.2

[2] * S. Arora and S. Safra: Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45:70–122, 1998. [JACM:10.1145/273865.273901]. 1

[3] * M. Bellare, O. Goldreich, and M. Sudan: Free bits, PCPs, and nonapproximability–towards tight results. SIAM Journal on Computing, 27:804–915, 1998. [SICOMP:10.1137/S0097539796302531]. 1, 2.3

[4] * U. Feige: A threshold of lnn for approximating set cover. Journal of the ACM, 45:634–652, 1998. [JACM:10.1145/285055.285059]. 1, 2.2

[5] * U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy: Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43:268–292, 1996. [JACM:10.1145/226643.226652]. 1

[6] * V. Guruswami, J. Håstad, and M. Sudan: Hardness of approximate hypergraph coloring. SIAM Journal on Computing, 31:1663–1686, 2002. [SICOMP:10.1137/S0097539700377165]. 1, 1 [7] * V. Guruswami, D. Levin, M. Sudan, and L. Trevisan: A tight characterization of NP

with 3 query PCPs. In Proceedings of 39th Annual IEEE Symposium of Foundations of Computer Science, pp. 8–17, 1998. [FOCS:10.1109/SFCS.1998.743424]. 1, 1, 3.2.3, 3.2.3

[8] * J. Håstad and S. Khot: Query efficient PCPs with perfect completeness. In In Proceedings of 42nd Annual IEEE Symposium of Foundations of Computer Science, pp. 610–619, 2001. [FOCS:10.1109/SFCS.2001.959937]. 1.1, 3.2.3

[9] * S. Khot: Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. In Proceedings of 42nd Annual IEEE Symposium of Foundations of Computer Science, pp. 600–609, 2001. [FOCS:10.1109/SFCS.2001.959936]. 1, 1.6, 5

[10] * S. Khot: Hardness results for coloring 3-colorable 3-uniform hypergraphs. In Proceedings of 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 23–32, 2002. [FOCS:10.1109/SFCS.2002.1181879]. 3.2.3

[11] * R. Raz: A parallel repetition theorem. SIAM Journal on Computing, 27:763–803, 1998. [SICOMP:10.1137/S0097539795280895]. 2.2

[12] * A. Samorodnitsky and L. Trevisan: A PCP characterization of NP with optimal amortized query complexity. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pp. 191–199, 2000. [STOC:10.1145/335305.335329]. 1, 2.2, 3.2, 3.2.2, 3.5

[13] * J. Håstad: Clique is hard to approximate within n^{1−ϵ} . Acta Mathematica, 182:105–142, 1999. [ActaMath:am182p01a00105]. 1

[14] * J. Håstad: Some optimal inapproximability results. Journal of the ACM, 48:798–859, 2001. [JACM:10.1145/502090.502098]. 1, 2.3.1, 3.1, 3.2.3

[15] * J. Håstad and A. Wigderson: Simple analysis of graph tests for linearity and PCP. Random Structures and Algorithms, 22:139–160, 2003. [RSA:10.1002/rsa.10068]. 1, 3.2, 5

[16] * L. Trevisan: Approximating satisfiable satisfiability problems. Algorithmica, 28:145–172, 2000. [Algorithmica:j2nhr52hrjr9bp55]. 1

AUTHORS

Johan Håstad professor Royal Institute of Technology, Stockholm, Sweden johanh nada kth se

 http://www.nada.kth.se/~johanh

Subhash Khot assistant professor Georgia Instiute of Technology, Atlanta GA 30332 khot cc gatech edu

http://www.cc.gatech.edu/~khot

ABOUT THE AUTHORS

Johan Håstad graduated from M.I.T. in 1986. His advisor was Shafi Goldwasser. He won the 1994 Gödel Prize for his work on circuit complexity. He is a member of the Royal Academy of Sciences (Sweden) and was an invited speaker at ICM 1998 and a plenary speaker at ECM 2004. His CS interests include cryptography, complexity theory and approximability of NP-hard optimization problems. He also enjoys table tennis and wine.

Subhash Khot graduated from Princeton University in 2003 under the supervision of Prof. Sanjeev Arora. He won the Best Student Paper award at FOCS 2003 and shared the Best Paper Award at FOCS 2004. He is interested in complexity theory, approximability of NP-hard problems and the theory of metric embeddings. He loves watching movies, cooking, and hanging out with friends and the family. Once an avid fan of cricket, he is not interested in the game anymore, thanks to the dismal performance of the Indian cricket team over the past several years.