Authors Johan H{\aa}stad, Subhash Khot,
License CC-BY-ND-2.0
T HEORY OF C OMPUTING, 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 + k2 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
2
at most 2−k + ε. 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 + k2 ,
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 work and grant Theory of Computing unlimited rights
to publish the work electronically and in hard copy. Use of the work 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.
c 2005 Johan Håstad and Subhash Khot DOI: 10.4086/toc.2005.v001a007
J. H ÅSTAD AND S. K HOT
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 + k2 bits, almost always accepts a correct proof of a correct statement and accepts
2
a proof of an incorrect statement with probability only marginally larger than 2−k . 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 + k2 in this case) and the logarithm of inverse of the error
probability (k2 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 87 + ε. 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.
Theorem 1.1. For any integer k > 0 and any ε > 0, any language in NP has a PCP verifier that queries
4k + k2 bits, has perfect completeness and accepts a proof of an incorrect statement with probability at
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 120
Q UERY E FFICIENT PCP S WITH P ERFECT C OMPLETENESS
2
most 2−k + ε.
Our result is based on a basic non-linear test which reads 5 bits (b1 , b2 , b3 , b4 , b5 ) from the proof
and accepts if b1 = b2 ⊕ b3 ⊕ (b4 ∧ b5 ). 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 12 + ε 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 con-
straints. There are stronger results for other constraints on 5 bits and in particular Guruswami et al. [7]
give a different predicate for which 12 can be improved to 167
.
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 2k−O( 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(2k /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 + k2 bits, has perfect completeness and accepts a proof of an incorrect statement with
2
probability at most 2−k + ε.
If we convert the test to be non-adaptive, this test would read 2k + 2k2 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 pk−O( k) on satisfiable instances.
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 121
J. H ÅSTAD AND S. K HOT
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 kc log k 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 sub-
tle 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: Sec-
tion 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
1 + x + y − xy
x ∧ y = AND(x, y) = .
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.
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 122
Q UERY E FFICIENT PCP S WITH P ERFECT C OMPLETENESS
Given a 3-SAT formula ϕ = C1 ∧C2 . . .∧Cm 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 Ck uniformly at random and a variable x j , again uniformly at random, appear-
ing in Ck . V sends k to prover P1 and j to prover P2 .
2. V receives a value for x j from P2 and values for all variables appearing in Ck from P1 . V accepts if
the two values for x j agree and the clause Ck 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 P1 and P2 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 (Cki )ui=1 uniformly at random and for each i, V chooses a variable x ji , again
uniformly at random, appearing in Cki . V sends (ki )ui=1 to prover P1 and ( ji )ui=1 to prover P2 .
2. V receives values for (x ji )ui=1 from P2 and values for all variables appearing in (Cki )ui=1 from P1 . V
accepts if the two values for x ji agree for each i and all the picked clauses are satisfied.
We let U denote the set of variables sent to P2 , i. e., (x ji )ui=1 while the set of variables that P1 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 dcu for some absolute
constant dc < 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 P1 and P2 can make
the verifier accept with probability greater than dcu . Here dc < 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 P1 or P2 , 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).
t
Thus the long code of a string of length t is a string of length 22 . 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.
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 123
J. H ÅSTAD AND S. K HOT
2.3.1 Fourier analysis
In this section, we explain the basics of the Fourier method. Let
F = f | {−1, 1}t → {−1, 1}
and consider the vector space of all “tables” A : F → R. Here the addition of two tables is defined as
t
pointwise addition and the dimension of this vector space is |F| = 22 . One can define a natural inner
product on this space by letting the inner product of two tables A1 and A2 be
hA1 , A2 i = 2−2 ∑ A1 ( f )A2 ( f ) .
t
f
For α ⊆ {−1, 1}t , let χα be a Boolean-valued (i. e., {−1, 1}-valued) table defined as
χα ( f ) = ∏ f (x) ∀ f ∈F .
x∈α
The χα are called characters. The characters are multiplicative, i. e.,
χα ( f1 f2 ) = χα ( f1 )χα ( f2 ) .
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 .
t
The set of characters (there are 22 of them) forms an orthonormal basis for the vector space. Thus
any table A can be expressed as
A( f ) = ∑ Âα χα ( f ) ,
α⊆{−1,1}t
where Âα are real numbers called Fourier coefficients; they can found as
Âα = hA, χα i = 2−2 ∑ Â( f )χα ( f ) .
t
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 α 6= 0,
/
E f [χα ( f )] = 0
while
E f [χ0/ ( f )] = 1 .
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 124
Q UERY E FFICIENT PCP S WITH P ERFECT C OMPLETENESS
Using this lemma together with (2.1) enables us to compute the expected value of products of char-
acters 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 Âα 6= 0 then |α| is odd and in particular α is non-empty.
Lemma 2.7. If A is conditioned upon h and Âα 6= 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 ) .
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 125
J. H ÅSTAD AND S. K HOT
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 P2 in the two-prover protocol. For each possible set U we ask the prover to write a
table, AU , which is supposed to be the long code of the answer by P2 on question U. We assume that AU
is folded over true.
Similarly W is the set of variables in the u clauses sent to P1 and let ϕW be the conjunction of the
clauses chosen. In the PCP we have a table, BW , which is a supposed to be the long code of the answer
of P1 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 0 on U uniformly at random (i. e., f , f 0 : {−1, 1}U → {−1, 1}).
3. V chooses two functions g and g0 on W uniformly at random (i. e., g, g0 : {−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))(g0 (y) ∧ f 0 (π(y))).
4. V accepts iff BW (h) = BW (g)AU ( f )(BW (g0 ) ∧ AU ( f 0 )).
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 BW (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 P1 and P2 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 AU and B instead of BW . Consider
the expression
1 + B(h)B(g)A( f )(B(g0 ) ∧ A( f 0 ))
.
2
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 126
Q UERY E FFICIENT PCP S WITH P ERFECT C OMPLETENESS
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 0 , g, g0 ,U, and W . The hypothesis of the
lemma implies that
E f , f 0 ,g,g0 ,U,W [B(h)B(g)A( f )(B(g0 ) ∧ A( f 0 ))] = δ . (3.1)
Fix U,W, f 0 and g0 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
∑ B̂β B̂β Âα E f ,g [χβ ( f g( f 0 ∧ g0 ))χβ (g)χα ( f )]
1 2 1 2
β1 ,β2 ,α
which, using (2.1) and Lemma 2.8, can be simplified to
∑ B̂β B̂β Âα E f ,g [χβ ( f 0 ∧ g0 )χβ ⊕β (g)χπ (β )⊕α ( f )] .
1 2 1 1 2 2 1
(3.2)
β1 ,β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β Âπ (β ) χβ ( f 0 ∧ g0 ) ,
2
β
and hence we need to analyze
E f 0 ,g0 [χβ ( f 0 ∧ g0 )(B(g0 ) ∧ A( f 0 ))] . (3.3)
We have a ∧ b = 12 (1 + a + b − ab) and thus (3.3) equals
1
E[χβ ( f 0 ∧ g0 )] + E[χβ ( f 0 ∧ g0 )B(g0 )] + E[χβ ( f 0 ∧ g0 )A( f 0 )] − E[χβ ( f 0 ∧ g0 )B(g0 )A( f 0 )] .
(3.4)
2
Fix the value of f 0 and let
β 0 = {y | y ∈ β ∧ f 0 (π(y)) = −1} .
When averaging over g0 , the first and third expected values in (3.4) are 0 unless β 0 = 0/ while the second
and the fourth expected values equal B̂β 0 and B̂β 0 A( f 0 ), respectively. To estimate the first and third terms
we note that the probability, over the choice of f 0 , that β 0 is empty is 2−|π(β )| . For the other terms we set
α = {x | x ∈ π(β ) ∧ f 0 (x) = −1}
and use the Cauchy-Schwarz inequality to obtain
!1/2
E f 0 |B̂β 0 | = 2−|π(β )| ∑ |B̂β ∩π (α) | ≤ 2−|π(β )|/2 ∑ B̂2β ∩π (α) ≤ 2−|π(β )|/2 .
−1 −1 (3.5)
α⊆π(β ) α⊆π(β )
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 127
J. H ÅSTAD AND S. K HOT
This implies that we get an overall upper bound on the left hand side of (3.1) as
" # " #
EU,W ∑ B̂2β |Âπ (β ) |(2−|π(β )| + 2−|π(β )|/2 ) ≤ EU,W ∑ B̂2β |Âπ (β ) |21−|π(β )|/2 ,
2 2
(3.6)
β β
and hence this expression is at least δ . We use this to establish good strategies for P1 and P2 . We first
establish that some parts of the given sum are small. We have the following result from [14, Lemma 6.9]
EU |π(β )|−1 ≤ |β |−c ,
(3.7)
1
where c is a constant and in fact c = 35 is possible. Note that the expectation is taken only over U and is
true for any W .
Let Sδ = (4(6 + 2 log δ −1 )/δ )1/c and consider any β of size at least Sδ . Since
E[|π(β )|−1 ] ≤ δ /4(6 + 2 log δ −1 )−1 ,
we conclude that the probability that |π(β )| ≤ (6 + 2 log δ −1 ) is upper bounded by δ /4. Thus for any β
of size at least Sδ we have
δ δ δ −1
EU [21−|π(β )|/2 ] ≤ Pr[|π(β )| ≤ (6 + 2 log δ −1 )] + 22+log δ + = ≤
4 4 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 P1 and P2 . On receiving W , P1 chooses β with
probability B̂2β and returns a random y ∈ β . Similarly on receiving a U, P2 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
" #
EU,W ∑ B̂2β Â2π (β ) |β |−1
2
. (3.8)
β
If we restrict summation to |β | ≤ Sδ and |Âπ2 (β ) | ≥ δ /4, (3.8) is at least
Sδ−1 δ /4 EU,W ∑ B̂2β |Âπ2 (β ) |
β ;|β |≤Sδ ,|Âπ2 (β ) |≥δ /4
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 (b1 , b2 , b3 , b4 , b5 ) of the proof and checks whether b1 b2 b3 (b4 ∧ b5 ) = 1
which is same as b1 = b2 ⊕ b3 ⊕ (b4 ∧ b5 ) 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.
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 128
Q UERY E FFICIENT PCP S WITH P ERFECT C OMPLETENESS
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
( fi )ki=1 and k functions ( f j0 )kj=1 and k sets (Wl )kl=1 each with its pair of functions (gl , g0l ). Each Wl is
picked uniformly from the set of possible companion in 2PP(u) to the already picked U. Thus for each
l, (U,Wl ) appears with the same probability as (U,W ) in 2PP(u). Note that Wl is not independent of Wl 0
for l 6= l 0 as they are companions of the same U.
We perform the basic test for a certain set of quadruples ( fi , f j0 , gl , g0l ). We give strong analyses in
two cases each utilizing k2 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 k2 quadruples is given by all triples (i, j, l) such that i + j + l = 0 mod k. 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 + k2 bits, has perfect completeness and soundness only
2
marginally higher than 2−k . 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 (Wl )kl=1 , that can appear with U in 2PP(u). Each Wl is chosen
with the distribution induced by 2PP(u), i. e., the distribution of the pair U,Wl is the same as the
distribution of U,W in 2PP(u).
3. V chooses 2k functions ( fi )ki=1 and ( f j0 )kj=1 on U uniformly at random.
4. For each l, 1 ≤ l ≤ k, V chooses two functions gl and g0l on Wl uniformly at random.
5. For each triple i, j, l such that i + j + l ≡ 0 mod k define a function hi jl by setting for each y ∈
{−1, 1}Wl , hi jl (y) = gl (y) fi (π(y))(g0l (y) ∧ f j0 (π(y))).
6. V accepts iff BWl (hi jl ) = BWl (gl )AU ( fi )(BWl (g0l ) ∧ AU ( f j0 )) for all i + j + l ≡ 0 mod k.
We have the following theorem.
2 Ω(u)
Theorem 3.3. The k-iterated almost disjoint sets test has completeness 1 and soundness 2−k + dc ,
where dc is the constant from Theorem 2.1 and u is the parameter of the underlying 2-prover protocol.
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 129
J. H ÅSTAD AND S. K HOT
Proof. The completeness follows from that of the basic test and we need to analyze the soundness. For
readability let us replace AU by A and BWl by Bl . Let Z0 denote the set of all triples (i, j, l) such that
i + j + l ≡ 0( mod k).
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) = Bl (hi jl )Bl (gl )A( fi )(A( f j0 ) ∧ Bl (g0l )) .
Consider
1 + Acc(i, j, l)
∏ = 2−k ∑ ∏ Acc(i, j, l) .
2
(3.9)
(i, j,l)∈Z
2 S⊆Z0 (i, j,l)∈S
0
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 = 0/ equals 1 and to establish the theorem
Ω(u)
it is sufficient to establish that any other term is bounded by dc . Let ΠS be the term corresponding to
S 6= 0/ and let TS be the expectation of ΠS . We go on to establish strategies for P1 and P2 which makes
the verifier in 2PP(u) accept with probability |TS |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 fi , i 6= k, f j0 , j 6= k and
(Wl , gl , g0l ) for l 6= k in such a way that the conditional expectation of ΠS remains at least TS . As the sets
in Z0 only intersect in one point we can, up to a factor ±1, write ΠS as
Acc(k, k, k) ∏ Acc(k, j, l) ∏ Acc(i, k, l) ∏ Acc(i, j, k) (3.10)
(k, j,l)∈S, j,l6=k (i,k,l)∈S,i,l6=k (i, j,k)∈S,i, j6=k
as the rest of the variables are fixed. The three products of (3.10) can be written as A(1) ( fk ), A(2) ( fk0 ) and
B(1) (gk , g0k ) respectively, for some Boolean functions A(1) , A(2) and B(1) .
Expanding the definition of Acc(k, k, k) and using x ∧ y = 1+x+y−xy 2 for A( fk0 ) ∧ Bk (g0k ) we see that
(3.10) can be written as the sum of four terms of the form
Bk (hkkk )A0 ( fk )A00 ( fk0 )C(gk , g0k ) , (3.11)
each with a coefficient 1/2, for some Boolean functions A0 , A00 and C closely related to A(1) , A(2) and
B(1) . To be more precise
A0 ( fk ) = A( fk )A(1) ( fk ) ,
A00 ( fk0 ) = A(2) ( fk0 ) or A00 ( fk0 ) = A( fk0 )A(2) ( fk0 ) ,
and
C(gk , g0k ) = Bk (gk )B(1) (gk , g0k ) or C(gk , g0k ) = Bk (gk )Bk (g0k )B(1) (gk , g0k ) .
We want to prove that if the expectation of (3.10) is large then the provers P1 and P2 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 P1 and P2 . 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.
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 130
Q UERY E FFICIENT PCP S WITH P ERFECT C OMPLETENESS
In the present situation the functions A0 and A00 depend only on U and the fixations made and hence
are available for player P2 to design a strategy. Bk is the original long code on Wk and hence is useful
for extracting a strategy for P1 . Finally C is a function that depends on both U and Wk and as this is not
fully known to either P1 or P2 , C is not useful for designing strategies.
Since we only have one remaining object of each type, let us for readability discard the index replac-
ing fk by f , Wk by W , etc.
We now want to compute the expected value of (3.11) over random choices of f , f 0 , g and g0 .
Expanding all factors except A00 ( f 0 ) by the Fourier transform we get
∑ Â0α B̂β Ĉγ,γ E f , f ,g,g χα ( f )χβ (g f ( f 0 ∧ g0 ))χγ (g)χγ (g0 )A00 ( f 0 )
0 0 0 0 . (3.12)
α,β ,γ,γ 0
Taking the expectation over f we see, using Lemma 2.3, that any term with α 6= π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 0 and considering expectation over g0 , we
see that only terms with γ 0 = β ∩ π −1 ( f 0−1 (−1)) remain nonzero.
This implies that (3.12) reduces to
" #
EU,W, f 0 ∑ Â0π (β ) B̂β Ĉβ ,β ∩π ( f (−1)) A00 ( f 0 )
2
−1 0−1 (3.13)
β
and, fixing U and W , let us estimate
" #
Ef0 ∑ Â0π (β ) B̂β Ĉβ ,β ∩π ( f (−1)) A00 ( f 0 ) .
2
−1 0−1 (3.14)
β
Towards this end we have
| E f 0 [Ĉβ ,β ∩π −1 ( f 0−1 (−1)) A00 ( f 0 )] | ≤ E f 0 [|Ĉβ ,β ∩π −1 ( f 0−1 (−1)) |] ≤ (3.15)
!1/2
2−|π(β )| ∑ |Ĉβ ,β ∩π (α ) | −1 0 ≤ 2−|π(β )|/2 ∑ Ĉβ2 ,β ∩π (α )−1 0 .
α 0 ⊆π(β ) α 0 ⊆π(β )
Substituting this estimate into (3.14) we get the upper estimate
!1/2
∑ |Â0π2 (β ) B̂β |2−|π(β )|/2 ∑ Ĉβ2 ,β ∩π −1 (α 0 ) (3.16)
β α 0 ⊆π(β )
and applying the Cauchy-Schwarz inequality over β this is bounded by
!1/2 !1/2 !1/2
∑ B̂2β Â02π (β ) 2−|π(β )|
2 ∑ Ĉβ2 ,β 1
≤ ∑ B̂2β Â02π (β ) 2−|π(β )|
2
, (3.17)
β β ,β1 β
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 131
J. H ÅSTAD AND S. K HOT
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
" #
EU,W ∑ B̂β Âπ2 (β ) 2
2 02 −|π(β )|
2
≥ EU,W |E f , f 0 ,g,g0 [ΠS ]|2 ≥ EU,W |E f , f 0 ,g,g0 [ΠS ]| ≥ E[ΠS ]2 ≥ TS2 .
β
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 Â02 0
π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 P2 picks α with probability Â02
α the set α might be empty. In this case P2 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 (Wl )kl=1 , that can appear with U in 2PP(u). Each Wl is chosen
with the distribution induced by 2PP(u), i. e., the distribution of the pair U,Wl is the same as the
distribution of U,W in 2PP(u).
3. V chooses 2k functions ( fi )ki=1 and ( fi0 )ki=1 on U uniformly at random.
4. For each l, 1 ≤ l ≤ k, V chooses two functions gl and g0l on Wl uniformly at random.
5. For each pair i, l define a function hil by setting for each y ∈ {−1, 1}Wl ,
hil (y) = gl (y) fi (π(y))(g0l (y) ∧ fi0 (π(y))) .
6. V accepts iff BWl (hil ) = BWl (gl )AU ( fi )(BWl (g0l ) ∧ AU ( fi0 )) for all 1 ≤ i, l ≤ k.
We have the following theorem.
2 Ω(u)
Theorem 3.4. The bipartite graph test has completeness 1 and soundness 2−k + dc .
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 Bl instead of BWl and A instead of AU . Also define
Acc(i, l) = Bl (hil )Bl (gl )A( fi )(A( fi0 ) ∧ Bl (g0l )) ,
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 132
Q UERY E FFICIENT PCP S WITH P ERFECT C OMPLETENESS
which is 1 if the test involving hil accepts and −1 if the test fails. Now we want to calculate the expected
value of
1 + Acc(i, l)
∏ = 2−k ∑ ∏ Acc(i, l) .
2
(3.18)
(i,l)∈[k]×[k]
2 S⊆[k]×[k] (i,l)∈S
Let TS 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 |TS |O(1) . We start by, as already done in [12], reducing to the case of
special S and let T2d 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 |TS | ≤ |T2d |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 ( fi , fi0 , gl , g0l )i,l=1,...,k into X given by choice of ( f1 , f10 ), and Y given by choice of the rest. Let
S1 be the subset of S given by (1, 1), (1, 2) . . . (1, d). Then
d
EX,Y [ ∏ Acc(i, l)] = EX,Y [∏ Acc(1, l) · ∏ Acc(i, l)] =
(i,l)∈S l=1 (i,l)∈S\S1
EX,Y [F(X,Y )G(Y )] = EY [EX [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
q q q
EY [(EX [F(X,Y )])2 ] EY [G(Y )2 ] ≤ EY [(EX [F(X,Y )])2 ] =
q q
EY [EX1 [F(X1 ,Y )] · EX2 [F(X2 ,Y )]] = EX1 ,X2 ,Y [F(X1 ,Y ) · F(X2 ,Y )]
where X1 , X2 are identically distributed as X and are independent. The proof is completed by the obser-
vation that F(X1 ,Y ) · F(X2 ,Y ) is equal to ∏dl=1 Acc(1, l) · ∏dl=1 Acc(2, l), which is exactly the same as
TS0 where S0 is a complete bipartite graph on [2] × [d].
Thus it is sufficient to find a good strategy based on |T2d | being large. Using the definition of Acc
and canceling the factors Bl (gl ) that appears exactly twice, we have
" #
d
T2d = E ∏ Bl (h1l )Bl (h2l )A( f1 )A( f2 )(A( f10 )A( f20 ) ∧ Bl (g0l )) . (3.19)
l=1
The function gl affects T2d only through h1l and h2l and replacing Bl (h1l ) and Bl (h2l ) by their Fourier
expansions we see that
Egl [Bl (h1l )Bl (h2l )] = ∑ B̂l,β B̂l,β Eg [χβ (gl f1 (g0l ∧ f10 ))χβ (gl f2 (g0l ∧ f20 ))] =
1 2 l 1 2
β1 ,β2
∑ B̂2l,β χβ ( f1 f2 )χβ ( f10 f20 ∧ g0l ) . (3.20)
β
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 133
J. H ÅSTAD AND S. K HOT
Substituting this into (3.19) we get
" ! #
d
E ∏ ∑ B̂2l,β χβ ( f1 f2 )χβ ( f10 f20 ∧ g0l ) A( f1 )A( f2 )((A( f10 )A( f20 )) ∧ Bl (g0l ))
l l l
. (3.21)
l=1 βl
Let us now consider the expectation over f1 and f2 . If d is even then the dependence of (3.21) on f1
and f2 is of the form
d
∏ χβ ( f1 f2 ) .
l
l=1
which has expected value 0 unless ⊕ j π2 (βl ) = 0/ while the expectation is 1 if we have equality.
If d is odd, then the dependence of f1 and f2 is of the form
d
A( f1 )A( f2 ) ∏ χβl ( f1 f2 ) .
l=1
Replacing A( f1 ) and A( f2 ) by their Fourier expansions we see that the expectation of this with respect
to f1 and f2 equals Â2α where
α = ⊕l π2 (βl ) .
Now let us turn to analyzing the rest of (3.21). First note that
d d
∏(A( f10 )A( f20 ) ∧ Bl (g0l )) = (A( f10 )A( f20 ) ∧ ∏ Bl (g0l )) .
l=1 l=1
We have (x ∧ y) = 1+x+y−xy
2 and we are now ready to consider the expectation over f10 and f20 and g0l . We
have expressions of the form
d d
(A( f10 )A( f20 ))a ∏ χβl ( f10 f20 ∧ g0l )(∏ Bl (g0l ))b , (3.22)
j=l l=1
for a, b ∈ {0, 1}. Now, view
d
C(g01 , g02 . . . g0d ) = (∏ Bl (g0l ))b
l=1
as a Boolean function with Fourier coefficients Ĉγ1 ,γ2 ,....γd , and thus (3.22) equals
d
∑ (A( f10 )A( f20 ))aĈγ1 ,γ2 ,....γd ∏ χβl ( f10 f20 ∧ g0l )χγl (g0l ) . (3.23)
γ1 ,γ2 ,...γl j=l
Let α 0 = ∪dl=1 π(βl ). For a fixed choice of f10 f20 = f 0 we get a nonzero expected value over (g0l )dl=1 iff
~β , f 0
γl = βl ∩ π −1 ( f 0−1 (−1)) for all l, giving a unique non-zero term. Defining γl to be this value we get
" #
d d
E f10 , f20 ,g01 ,g02 ,...g0d (A( f10 )A( f20 ))a ∏ χβl ( f10 f20 ∧ g0l )(∏ Bl (g0l ))b ≤ (3.24)
j=l l=1
0
E f10 , f20 Ĉ ~β , f 0 ~β , f 0 ~β , f 0 ≤ 2−|α |/2 , (3.25)
γ1 ,γ2 ,....γd
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 134
Q UERY E FFICIENT PCP S WITH P ERFECT C OMPLETENESS
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
d
∑ ∏ B̂2l,β 2−|α |/2
0
l
(3.26)
⊕l π2 (βl )=0/ l=1
for |T2d | while in the case when d is odd we get
d
∑ Â2⊕l π2 (βl ) ∏ B̂2l,βl 2−|α |/2 ,
0
(3.27)
l=1
where in both cases we have α 0 = ∪dl=1 π(βl ).
Strategies for the provers can now be defined as follows. P1 upon receiving W , picks β with proba-
bility B̂2β and returns a random y ∈ β . P2 upon receiving U picks d − 1 random Wl , l = 2 . . . d and picks
β2 , . . . βd with probability ∏dl=2 B̂2l,βl and computes α 00 = ⊕dl=2 π2 (βl ). If d is even P2 returns a random
x ∈ α 00 . If d is odd P2 also picks α with probability Â2α and returns a random element in α 00 ⊕ α. 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
d
∑ ∏ B̂2l,β (∑ |βl |)−1
l
(3.28)
⊕l π2 (βl )=0/ l=1
and in the case of odd d it as at least
d
∑ Â2⊕l π2 (βl ) ∏ B̂2l,βl (∑ |βl |)−1 . (3.29)
l=1
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
|T2d |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
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 + k2 bits in the adaptive setting and 2k + 2k2
bits in the non-adaptive setting. It has perfect completeness and it turns out that soundness is essentially
2
2−k 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
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 135
J. H ÅSTAD AND S. K HOT
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 P1 , with high probability the answers by P2 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 Tu clauses (Cki )Tui=1 uniformly at random. Then he randomly selects u clauses (C ji )i=1
u
out of these Tu clauses and randomly selects a variable x ji from each clauses C ji . He sends (ki )Tu
i=1
to prover P1 ; and to prover P2 , he sends the u chosen variables (x ji )ui=1 together with the (T − 1)u
clauses not selected.
2. V receives values for the u chosen variables (x ji )ui=1 from P2 as well as 3(T − 1)u values for the
variables in the clauses sent to P2 . V also receives 3Tu values from P1 to the variables in the clauses
sent to P1 . 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 dcu .
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 )kj=1 , 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 ( fi )ki=1 on U uniformly at random and reads the bits AU ( fi ).
4. For each j, 1 ≤ j ≤ k, V chooses a function g j on W j uniformly at random and reads the bits
BW j (g j ).
5. For each pair i, j define a function hi j by setting, independently, for each y ∈ {−1, 1}W j , hi j (y) =
−1 with probability 1 − ε and otherwise hi j (y) = 1.
6. For each pair i, j, if A( fi ) = 1, V checks that B j (g j ( fi ∧ hi j )) = B j (g j ) and otherwise V checks
that B j (g j (− fi ∧ hi j )) = 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.
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 136
Q UERY E FFICIENT PCP S WITH P ERFECT C OMPLETENESS
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( fi ) = 1 then fi (π U (z)) = 1 and we have
B j (g j ( fi ∧ hi j )) = g j (π W (z))( fi (π U (z)) ∧ hi j (π W (z))) = g j (π W (z)) = B j (g j ) .
The case A( fi ) = −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
2
iterated test with parameter ε accept with probability 2−k + 2δ where δ > 6ε. Then we can find
strategies for P1 and P2 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
1
Acc(i, j) = ((1 + A( fi ))B j (g j )B j (g j ( fi ∧ hi j )) + (1 − A( fi ))B j (g j )B j (g j (− fi ∧ hi j ))) ,
2
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 ∏ Acc(i, j) ≥ 2δ . (3.30)
(i, j)∈S
As all coordinates are symmetric we may assume that (1, 1) ∈ S. Now fix the values of g j and fi for
i, j ≥ 2 and hi j for (i, j) 6= (1, 1) to any constants without decreasing the expected value obtaining
h i
(1) (1)
EU,W1 , f1 ,g1 ,h11 Acc(1, 1)A ( f1 )B (g1 ) ≥ 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
A0 ( f1 )B(g1 ( f1 ∧ h11 ))C(g1 ) (3.32)
or
A0 ( f1 )B(g1 (− f1 ∧ h11 ))C(g1 ) (3.33)
whose expectation over the choice of U, f1 , W1 , g1 and h11 is at least δ . Here A0 , B and C are Boolean
functions where B is the original B1 and A0 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
" #
EU,W, f ,g,h ∑ Â0α B̂β Ĉγ χα ( f )χβ (g( f ∧ h))χγ (g) . (3.34)
α,β ,γ
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 137
J. H ÅSTAD AND S. K HOT
Taking expectation over g we see that terms with β 6= γ have expectation 0 and thus (3.34) equals
" #
EU,W ∑ Âα B̂β Ĉβ E f ,h χα ( f )χβ (( f ∧ h))
0
. (3.35)
α,β
If α 6⊆ π(β ) 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 ∏ f (x) ∏ ( f (x) ∧ h(y)) ∏ ∏ ( f (x) ∧ h(y)) (3.37)
x∈α y∈β ∩π −1 (x) x∈π(β )\α y∈β ∩π −1 (x)
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
∏ ( f (x) ∧ h(y))) = 1 ,
y∈β ∩π −1 (x)
while while if f (x) = −1, it has expectation over h that equals (2ε − 1)sx where sx = |π −1 (x) ∩ β |. We
conclude that the expectation of (3.37) equals
1 1
∏ ( (1 − (2ε − 1)sx )) ∏ ( (1 + (2ε − 1)sx )) ,
2 2
x∈α∩π(β ) x∈π(β )\α
and defining this expression to be p(α, β ), we conclude that (3.35) equals
" #
EU,W ∑ Â0α B̂β Ĉβ p(α, β ) . (3.38)
β ,α⊆π(β )
By assumption this expectation is at least δ and we need to design strategies for P1 and P2 .
The strategies of the two provers are the standard strategies. i. e., P2 chooses an α with probability
02
Âα and returns a random x ∈ α. Similarly P1 chooses a random β with probability B̂2β and returns a
random y ∈ β . Again A0 cannot be assumed to be folded as it is a derived table. If α is the empty set
we do not care what P2 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
" #
EU,W ∑ Â02 2
α B̂β |β |
−1
. (3.39)
β ,06/ =α⊆π(β )
We need to prove that this is large based on (3.38) being at least δ .
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 138
Q UERY E FFICIENT PCP S WITH P ERFECT C OMPLETENESS
First note that
!1/2 !1/2
∑ |B̂β Ĉβ | ≤ ∑ B̂2β ∑ Ĉβ2 ≤1 , (3.40)
β β β
and the quantity that multiplies B̂β Ĉβ in (3.38) satisfies
!1/2 !1/2
∑ Â0α p(α, β ) ≤ ∑ Â02
α ∑ p (α, β )
2
α⊆π(β ) α⊆π(β ) α⊆π(β )
!1/2
≤ ∑ p (α, β )2
≤ (1 − ε)|π(β )|/2 . (3.41)
α⊆π(β )
To see the last inequality in (3.41) note that the sum equals
2 2 !
1 1
∏ 2
(1 − (2ε − 1)sx ) +
2
(1 + (2ε − 1)sx ) . (3.42)
x∈π(β )
The factor corresponding to x in (3.42) is of the form a2 +b2 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
|β |2
PrU [|π(β )| < |β |] < . (3.43)
2T
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
−2 −1
(1 − ε)ε ≤ eε ≤ ε .
We conclude that
" # " #
EU,W ∑ Â0α B̂β Ĉβ p(α, β ) ≤ EU,W ∑ B̂β Ĉβ (Pr[|π(β )| ≤ 2ε −1 ] + ε) ≤ 3ε. (3.44)
|β |≥2ε −2 ,α⊆π(β ) |β |≥2ε −2
It follows that
" #
EU,W ∑ Â0α B̂β Ĉβ p(α, β ) ≥ δ − 3ε , (3.45)
|β |≤2ε −2 ,α⊆π(β )
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 139
J. H ÅSTAD AND S. K HOT
and we want to bound the contribution from α = 0./ Note that if |β | ≤ 2ε −2 then, by Lemma 3.8, except
with probability 2ε each sx is one. In this case
/ β ) = ε |β | ≤ ε
p(0,
and we conclude that the total expectation of terms containing α = 0/ is at most 3ε and hence we have
" #
EU,W ∑ Â0α B̂β Ĉβ p(α, β ) ≥ δ − 6ε . (3.46)
|β |≤2ε −2 ,06/ =α⊆π(β )
Returning to (3.39) we see that the provers are successful with with probability at least
" #
ε2
2
EU,W ∑ Â02 2
α B̂β .
β ,06/ =α⊆π(β ),|β |≤2ε −2
Now by the above reasoning we have the following chain of equalities, where all sums are over the set
{β , 0/ 6= α ⊆ π(β ), |β | ≤ 2ε −2 } :
(δ − 6ε)2 ≤ EU,W ∑ Â0α B̂β Ĉβ p(α, β ) ≤ EU,W ∑ Â0α B̂β Ĉβ p(α, β )
2 h 2 i
≤
EU,W ∑ Â02 ∑ Ĉβ2 p2 (α, β ) ≤ EU,W ∑ Â02α B̂2β ,
h i h i
2
α B̂β
where the last inequality follows from
∑ ∑ Ĉβ2 p2 (α, β ) ≤ ∑ Ĉβ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 Z p denote the multiplicative group given by the pth roots of unity. Let ζ = e2πi/p be the basic pth
root of unity. To generalize the Boolean ∧ we define an operation mult( , ) as:
mult(ζ i , ζ j ) = ζ i j .
We have the following useful lemma
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 140
Q UERY E FFICIENT PCP S WITH P ERFECT C OMPLETENESS
Lemma 4.1. If x and y are pth roots of unity, we have
1 p−1 p−1 i j −i j
mult(x, y) = ∑ ∑xy ζ .
p i=0 j=0
Proof. Suppose y = ζ i0 . Fix i and consider the inner sum. For i 6= i0 the value is 0 while for i = i0 it is
p. This implies that the total sum equals xi0 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 → Z p and in the code for x this position takes value f (x).
Let A be a table containing a value A( f ) ∈ Z p for every function f : {−1, 1}t → Z 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 ) = ∏ f (x)α(x) .
x∈{−1,1}t
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) 6= 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 Âα 6= 0, then ∑x∈{−1,1}t α(x) = 1 mod p. In particular N(α)
is a nonempty set.
Lemma 4.6. If A is conditioned upon a function h : {−1, 1}t → {1, ζ } and Âα 6= 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 Q(ζ ), the rational numbers with the
pth root of unity added. We use the homomorphism σa , 0 ≤ a ≤ p − 1 which has the property that
σa (ζ i ) = ζ ia . For x a pth root of unity we have σa (x) = xa but this is not true in general.
We have the following straightforward lemma of which we omit the proof.
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 141
J. H ÅSTAD AND S. K HOT
Lemma 4.7. For x 6= 1 a pth root of unity we have
p−1
∑ σa (x) = 0 .
a=0
Finally define
π p (β )(x) = ∑ β (y) mod p
y∈π −1 (x)
as the generalization of π2 . Lemma 2.8 generalizes.
Lemma 4.8. Let β ⊆ {−1, 1}W , U ⊆ W and f : {−1, 1}U → Z 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 0 on U, taking values in Z p uniformly at random.
3. V chooses two random functions g and g0 on W taking values in Z 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(g0 (y), f 0 (π(y))).
4. V accepts iff B(h) = B(g)A( f ) mult(B(g0 ), A( f 0 )).
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 P1 and P2 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(g0 ), A( f 0 ))
is a pth root of unity which is 1 iff the test accepts.
This implies, under the hypothesis of the lemma and using Lemma 4.7, that
p−1
EU,W, f , f 0 ,g,g0 [ ∑ σa (B(h)−1 B(g)A( f ) mult(B(g0 ), A( f 0 )))] = δ .
a=1
Using Lemma 4.1 and the fact that our tables respect exponentiation we see that
p−1 p−1 p−1
EU,W, f , f 0 ,g,g0 [ ∑ ∑ ∑ B(h)−a B(ga )A( f a )B(g0ab )A( f 0ac )ζ −bc ] = pδ .
b=0 c=0 a=1
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 142
Q UERY E FFICIENT PCP S WITH P ERFECT C OMPLETENESS
We conclude that there must be some value of (a, b, c) such that
|EU,W, f , f 0 ,g,g0 [B(h)−a B(ga )A( f a )B(g0ab ), A( f 0ac )]| ≥ p−2 δ . (4.1)
Replacing (h, g, f , g0 , f 0 ) by (ha , ga , f a , g0a , f 0) preserves probability and hence changing the value of c,
we can without loss of generality assume that a = 1.
Fix U,W, f 0 and g0 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
∑ B̂β B̂β Âα E f ,g [χβ ( f −1 g−1 mult( f 0 , g0 )−1 )χβ (g)χα ( f )] .
1 2 1 2
β1 ,β2 ,α
The inner expected value is 0 unless β1 = β2 and π p (β1 ) = α and hence (4.2) equals
∑ B̂2β Âπ (β ) χβ (mult( f 0 , g0 )−1 ) .
p
(4.3)
β
Returning to (4.1) we need to analyze
E f 0 ,g0 [χβ (mult( f 0 , g0 )−1 )B(g0b )A( f 0c )] . (4.4)
Fix the value of f 0 . When b = 0, averaging over g0 gives 0 unless f 0 (π(z)) = 1 for all z ∈ N(β ). The
probability of picking such an f 0 is p−|π(N(β ))| . Now consider the case when b 6= 0. Define β 0 as follows:
for every y, β 0 (y) = b−1 e(y)β (y) where f 0 (π(y)) = ζ e(y) . Averaging (4.4) over g0 yields B̂β 0 A( f 0c ).
We note that f 0 s which are different on π(N(β )) give different β 0 . Let ∆β be the set of all possible
β . We have |∆β | = p|π(N(β ))| and over all the choices of f 0 , every β 0 ∈ ∆β occurs equally often. Using
0
this observation and applying the Cauchy-Schwarz inequality gives
| E f 0 [B̂β 0 A( f 0c )] | ≤ E f 0 [|B̂β 0 |] = p−|π(N(β ))| ∑ |B̂β 0 | ≤
β 0 ∈∆β
1/2
p−|π(N(β ))|/2 ∑ |B̂β 0 |2 ≤ p−|π(N(β ))|/2 .
β 0 ∈∆β
This implies that we get an overall upper bound on the expectation of (4.1) as
" #
EU,W ∑ |B̂β |2 |Âπ (β ) | p−|π(N(β ))|/2
p
.
β
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(β ) ).
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 143
J. H ÅSTAD AND S. K HOT
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 (Wl )kl=1 , that can appear with U in 2PP(u). Each Wl is chosen
with the distribution induced by 2PP(u), i. e., the distribution of the pair U,Wl is the same as the
distribution of U,W in 2PP(u).
3. V chooses 2k functions ( fi )ki=1 and ( f j0 )kj=1 on U taking values in Z p uniformly at random.
4. For each l, 1 ≤ l ≤ k, V chooses two functions gl and g0l on Wl taking values in Z p uniformly at
random.
5. For each triple i, j, l such that i + j + l ≡ 0 mod k define a function hi jl by setting for each y ∈
{−1, 1}Wl , hi jl (y) = gl (y) fi (π(y)) mult(g0l (y), f j0 (π(y))).
6. V accepts iff BWl (hi jl ) = BWl (gl )AU ( fi ) mult(BWl (g0l ), AU ( f j0 )) for all i + j + l ≡ 0 mod k.
We have the following theorem.
2 Ω(u)
Theorem 4.10. The almost disjoint sets test in Z p has completeness 1 and soundness p−k + pO(1) dc ,
where dc 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) = Bl (hi jl )−1 Bl (gl )A( fi ) mult(A( f j0 ), Bl (g0l )) ,
which is 1 if the test associated with (i, j, l) accepts and otherwise it is a different pth root of unity.
2
Let Z0 be the set of all triples (i, j, l) with i + j + l ≡ 0( mod k) and let S ∈ GF(p)k be a vector
whose coordinates are indexed by the triples in Z0 . We have
p−1
∑ (Acc(i, j, l))a
∏ a=0 p ∑ ∏ (Acc(i, j, l))S(i, j,l) .
2
= p−k
(i, j,l)∈Z 2
0 S∈GF(p)k (i, j,l)∈Z0
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
Ω(u)
to establish that any term with S 6≡ 0 is upper bounded above by pO(1) dc . Let TS be the expected value
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 144
Q UERY E FFICIENT PCP S WITH P ERFECT C OMPLETENESS
of the term corresponding to S. We go on to establish a strategy for P1 and P2 which makes the verifier
in 2PP(u) accept with probability p−O(1) |TS |O(1) .
Suppose without loss of generality that S(k, k, k) = r 6= 0 and fix the values of fi , i 6= k, f j , j 6= k and
(Wl , gl , g0l ) for l 6= k in such a way as not to decrease |TS |. 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 TS , after the above fixings, can be written as the sum of p2 terms of the form
B(h)−r A0 ( f )A00 ( f 0 )C(g, g0 ) , (4.5)
each with a coefficient of complex absolute value 1/p. Here A0 , A00 , B, and C takes values which are pth
roots of unity. We conclude that there is such an expression of the form (4.5) whose expectation over
U,W, h, f , f 0 , g, and g0 is at least |TS |/p.
Here A0 and A00 are functions that only depend on U and hence might be used to extract strategy for
P2 . B is the original long p-code on W = Wk and hence is useful for extracting strategy for P1 .
We now want to compute the expected value of this expression over random choices of f , f 0 , g and
g0 . Expanding all factors except A00 ( f 0 ) by the Fourier transform we get
∑ Â0α B̂β Ĉγ,γ E[χα ( f )χ−rβ (g f mult( f 0 , g0 ))χγ (g)χγ (g0 )A00 ( f 0 )] .
0 0 (4.6)
α,β ,γ,γ 0
Now taking the expected value over f we see that unless α = rπ p (β ) the term is 0. Similarly we need
γ = rβ . Fix f 0 and define β 0 as follows: for every y, β 0 (y) = re(y)β (y) where f 0 (π(y)) = ζ e(y) . With
this definition, we have
χ−rβ (mult( f 0 , g0 )) = χ−β 0 (g0 ) .
Thus unless γ 0 = β 0 , the expectation is 0. Thus (4.6) equals
∑ Â0 rπ (β ) B̂β Ĉβ ,β A00 ( f 0 ) .
p
0 (4.7)
β
Note that β 0 is uniquely determined by β and f 0 and functions f 0 which are different on π(N(β )) give
different β 0 s. Let ∆β be the set of all possible β 0 s. We have |∆β | = p|π(N(β ))| and over all the choices of
f 0 , every β 0 ∈ ∆β occurs equally often. This implies that
| E f 0 [Ĉβ ,β 0 (β , f 0 ) A00 ( f 0 )] | ≤ E f 0 [|Ĉβ ,β 0 (β , f 0 ) |] ≤ (4.8)
p−|π(N(β ))| ∑ |Ĉβ ,β 0 | ≤ p−|π(N(β ))|/2 ( ∑ |Ĉβ ,β 0 |2 )1/2 .
β 0 ∈∆β β 0 ∈∆β
Substituting this estimate into (4.7) and using the Cauchy-Schwarz inequality over β we get the upper
estimate
!1/2 1/2 !1/2
∑ |B̂β | |Â
2 0 2 −|π(N(β ))|
| p
rπ p (β )
∑ |Ĉβ ,β 0 | ≤ ∑ |B̂β | |Â
2 2 0 2
| p−|π(N(β ))|
rπ p (β )
β β ,β 0 ∈∆β β
for |TS |/p. The same strategy as defined in the basic test now makes the verifier accept in 2PP(u) with
probability p−O(1) |TS |O(1) and the theorem follows.
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 145
J. H ÅSTAD AND S. K HOT
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. A RORA , C. L UND , R. M OTWANI , M. S UDAN , AND M. S ZEGEDY: Proof verifica-
tion and the hardness of approximation problems. Journal of the ACM, 45:501–555, 1998.
[JACM:10.1145/278298.278306]. 1, 2.2
[2] * S. A RORA AND S. S AFRA: 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. B ELLARE , O. G OLDREICH , AND M. S UDAN: 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. F EIGE: A threshold of ln n for approximating set cover. Journal of the ACM, 45:634–652,
1998. [JACM:10.1145/285055.285059]. 1, 2.2
[5] * U. F EIGE , S. G OLDWASSER , L. L OVASZ , S. S AFRA , AND M. S ZEGEDY: Interactive
proofs and the hardness of approximating cliques. Journal of the ACM, 43:268–292, 1996.
[JACM:10.1145/226643.226652]. 1
[6] * V. G URUSWAMI , J. H ÅSTAD , AND M. S UDAN: Hardness of approximate hypergraph coloring.
SIAM Journal on Computing, 31:1663–1686, 2002. [SICOMP:10.1137/S0097539700377165]. 1,
1
[7] * V. G URUSWAMI , D. L EVIN , M. S UDAN , AND L. T REVISAN: 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
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 146
Q UERY E FFICIENT PCP S WITH P ERFECT C OMPLETENESS
[8] * J. H ÅSTAD AND S. K HOT: Query efficient PCPs with perfect completeness. In In Proceed-
ings 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. K HOT: 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. K HOT: Hardness results for coloring 3-colorable 3-uniform hypergraphs. In Proceed-
ings 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. R AZ: A parallel repetition theorem. SIAM Journal on Computing, 27:763–803, 1998.
[SICOMP:10.1137/S0097539795280895]. 2.2
[12] * A. S AMORODNITSKY AND L. T REVISAN: A PCP characterization of NP with optimal amor-
tized query complexity. In Proceedings of the 32nd Annual ACM Symposium on Theory of Com-
puting, 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 n1−ε . 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. W IGDERSON: 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. T REVISAN: 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
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 147
J. H ÅSTAD AND S. K HOT
ABOUT THE AUTHORS
J OHAN 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.
S UBHASH K HOT 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.
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 119–148 148