A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.
The current proof of the probabilistically checkable proofs (PCP) theorem (i.e., ${\cal NP}={\cal PCP}(\log,O(1))$) is very complicated. One source of difficulty is the technically involved analysis of low-degree tests. Here, we refer to the difficulty of obtaining strong results regarding low-degree tests; namely, results of the type obtained and used by Arora and Safra [J. ACM, 45 (1998), pp. 70--122] and Arora et al. [J. ACM, 45 (1998), pp. 501--555].In this paper, we eliminate the need to obtain such strong results on low-degree tests when proving the PCP theorem. Although we do not remove the need for low-degree tests altogether, using our results it is now possible to prove the PCP theorem using a simpler analysis of low-degree tests (which yields weaker bounds). In other words, we replace the strong algebraic analysis of low-degree tests presented by Arora and Safra and Arora et al. by a combinatorial lemma (which does not refer to low-degree tests or polynomials).
Introduction
The characterization of NP in terms of Probabilistically Checkable Proofs (PCP systems) [AS,
ALMSS], hereafter referred to as the PCP Characterization Theorem, is one of the more fundamental
achievements of complexity theory. Loosely speaking, this theorem states that membership in
any NP-language can be verified probabilistically by a polynomial-time machine which inspects
a constant number of bits (in random locations) in a "redundant" NP-witness. Unfortunately,
the current proof of the PCP Characterization Theorem is very complicated and, consequently, it
has not been assimilated into complexity theory. Clearly, changing this state of affairs is highly
desirable.
There are two things which make the current proof (of the PCP Characterization Theorem)
difficult. One source of difficulty is the complicated conceptual structure of the proof (most notably
the acclaimed 'proof composition' paradigm). Yet, with time, this part seems easier to understand
and explain than when it was first introduced. Furthermore, the Proof Composition Paradigm
turned out to be very useful and played a central role in subsequent works in this area (cf., [BGLR,
BS, BGS, H96]). The other source of difficulty is the technically involved analysis of low-degree
tests. Here we refer to the difficulty of obtaining strong results regarding low-degree tests; namely,
results of the type obtained and used in [AS] and [ALMSS].
In this paper, we eliminate the latter difficulty. Although we do not get rid of low-degree
tests altogether, using our results it is now possible to prove the PCP Characterization Theorem
using only the weaker and simpler analysis of low-degree tests presented in [GLRSW, RS92, RS96].
In other words, we replace the complicated algebraic analysis of low-degree tests presented in
[AS, ALMSS] by a combinatorial lemma (which does not refer to low-degree tests or even to
polynomials). We believe that this combinatorial lemma is very intuitive and find its proof much
simpler than the algebraic analysis of [AS, ALMSS]. (However, simplicity may be a matter of
taste.)
Loosely speaking, our combinatorial lemma provides a way of generating sequences of pairwise
independent random points so that any assignment of values to the sequences must induce consistent
values on the individual elements. This is obtained by a "consistency test" which samples a constant
number of sequences. We stress that the length of the sequences as well as the domain from which
the elements are chosen are parameters, which may grow while the number of samples remains
fixed.
1.1 Two Combinatorial Consistency Lemmas
The following problem arises frequently when trying to design PCP systems, and in particular when
proving the PCP Characterization Theorem. For some sets S and V , one has a procedure, which
given (bounded) oracle access to any function f : S 7! V , tests if f has some desired property.
Furthermore, in case f is sufficiently bad (i.e., far from any function having the property), the test
detects this with "noticeable" probability. For example, the function f may be the proof-oracle
in a basic PCP system which we want to utilize (as an ingredient in the composition of PCP
systems). The problem is that we want to increase the detection probability (equivalently, reduce
the error probability) without increasing the number of queries, although we are willing to allow
more informative queries. For example, we are willing to allow queries in which one supplies a
sequence of elements in S and expects to obtain the corresponding sequence of values of f on these
elements. The problem is that the sequences of values obtained may not be consistent with any
We can now phrase a simple problem of testing consistency. One is given access to a function
and is asked whether there exists a function f : S 7! V so that for most sequences
Loosely speaking, we prove that querying F on a constant number of related random sequences
suffices for testing a relaxion of the above. That is,
Lemma 1.1 (combinatorial consistency - simple case): For every ffi ? 0, there exists a constant
poly(1=ffi) and a probabilistic oracle machine, T , which on input ('; jSj) runs for poly(' \Delta log jSj)-
time and makes at most c queries to an oracle F : S ' 7!V ' , such that
ffl If there exist a function f : S 7! V such that F
accepts when given access to oracle F .
ffl If T accepts with probability at least 1
access to oracle F , then there exist a
such that the sequences F agree on at least
' positions, for at least a fraction of all possible
Specifically, the test examines the value of the function F on random pairs of sequences ((r
' of the i's, and checks that the corresponding values (on these r i 's and s i 's)
are indeed equal. For details see Section 4.
Unfortunately, this relatively simple consistency lemma does not suffice for the PCP appli-
cations. The reason being that, in that application, error reduction (see above) is done via
randomness-efficient procedures such as pairwise-independent sequences (since we cannot afford
to utilize ' \Delta log 2
jSj random bits as above). Consequently, the function F is not defined on the
entire set S ' but rather on a very sparse subset, denoted S. Thus, one is given access to a function
and is asked whether there exists a function f : S 7! V so that for most sequences
the sequences F agree on most (continious) subsequences
of length
'. The main result of this paper is
Lemma 1.2 (combinatorial consistency - sparse case): For every two of integers s; ' ? 1, there
exists a set S s;' ae [s] ' , where [s] so that the following holds:
1. For every ffi ? 0, there exists a constant c = poly(1=ffi) and a probabilistic oracle machine, T ,
which on input ('; s) runs for poly(' \Delta log s)-time and makes at most c queries to an oracle
, such that
ffl If there exist a function f : [s] 7! V such that F
accepts when given access to oracle F .
ffl If T accepts with probability at least 1
access to oracle F , then there exist a
such that for at least a fraction of all possible
the sequences F agree on at least a fraction of the
subsequences of length
'.
2. The individual elements in a uniformly selected sequence in S s;' are uniformly distributed in
[s] and are pairwise independent. Furthermore, the set S s;' has cardinality poly(s) and can
be constructed in time poly(s; ').
Specifically, the test examines the value of the function F on related random pairs of sequences
These sequences are viewed as
' \Theta
' matrices, and, loosely
speaking, they are chosen to be random extensions of the same random row (or column). For
details see Section 2.
In particular, the presentation in Section 2 axiomatizes properties of the set of sequences, S s;' ,
for which the above tester works. Thus, we provide a "parallel repetition theorem" which holds for
random but non-independent instances (rather than for independent random instances as in other
such results). However, our "parallel repetition theorem" applies only to the case where a single
query is asked in the basic system (rather than a pair of related queries as in other results). Due to
this limitation, we could not apply our "parallel repetition theorem" directly to the error-reduction
of generic proof systems. Instead, as explained below, we applied our "parallel repetition theorem"
to derive a relatively strong low-degree test from a weaker low-degree test.
We believe that the combinatorial consistency lemma of Section 2 may play a role in subsequent
developments in the area.
1.2 Application to the PCP Characterization Theorem
The currently known proof of the PCP Characterization Theorem [ALMSS] composes proof systems
in which the verifier makes a constant number of multi-valued queries. Such verifiers are constructed
by "parallelization" of simpler verifiers, and thus the problem of "consistency" arises. This problem
is solved by use of low-degree multi-variant polynomials, which in turn requires "high-quality" low-degree
testers. Specifically, given a function f : GF(p) n 7! GF(p), where p is prime, one needs to
test if f is close to some low-degree polynomial (in n variables over the finite field GF(p)). It is
required that any function f which disagrees with every d-degree polynomial on at least (say) 1%
of the inputs be rejected with (say) probability 99%. The test is allowed to use auxiliary proof
oracles (in addition to f) but it may only make a constant number of queries and the answers must
have length bounded by poly(n; d; log p). Using a technical lemma due to Arora and Safra [AS],
Arora et. al. [ALMSS] proved such a result. 1 The full proof is quite complex and is algebraic in
nature. A weaker result due to Gemmel et. al. [GLRSW] (see [RS96]) asserts the existence of a
d-degree test which, using d+2 queries, rejects such bad functions with probability at
Their proof is much simpler. Combining the result of Gemmel et. al. [GLRSW, RS96] with our
combinatorial consistency lemma (i.e., Lemma 1.2), we obtain an alternative proof of the following
result
Lemma 1.3 (low-degree tester): For every ffi ? 0, there exists a constant c and a probabilistic
oracle machine, T , which on input n; p; d runs for poly(n; d; log p)-time and makes at most c queries
to both f and to an auxiliary oracle F , such that
ffl If f is a degree-d polynomial, then there exist a function F so that T always accepts.
ffl If T accepts with probability at least 1
access to the oracles f and F , then f
agrees with some degree-d polynomial on at least a 1
fraction of the domain. 2
We stress that in contrast to [ALMSS] our proof of the above lemma is mainly combinatorial. Our
only reference to algebra is in relying on the result of Gemmel et. al. [GLRSW, RS96] (which is
An improved analysis was later obtained by Friedl and Sudan [FS].
Actually, [ALMSS] only prove agreement on an (arbitrary large) constant fraction of the domain.
weaker and has a simpler proof than that of [ALMSS]). Our tester works by performing many (pair-
wise independent) instances of the [GLRSW] test in parallel, and by guaranteeing the consistency
of the answers obtained in these tests via our combinatorial consistency test (i.e., of Lemma 1.2).
In contrast, prior to our work, the only way to guarantee the consistency of these answers resulted
in the need to perform a low-degree test of the type asserted in Lemma 1.3 (and using [ALMSS],
which was the only alternative known, this meant losing the advantage of utilizing a low-degree
tests with a simpler algebraic analysis).
1.3 Related work
We refrain from an attempt to provide an account of the developments which have culminated in
the PCP Characterization Theorem. Works which should certainly be mentioned include [GMR,
BGKW, FRS, LFKN, S90, BFL, BFLS, FGLSS, AS, ALMSS] as well as [BF, BLR, LS, RS92]. For
detailed accounts see surveys by Babai [B94] and Goldreich [G96].
Hastad's recent work [H96] contains a combinatorial consistency lemma which is related to our
Lemma 1.1 (i.e., the "simple case" lemma). However, Hastad's lemma refers to the case where the
test accepts with very low probability and so its conclusion is weaker (though harder to establish).
Raz and Safra [RaSa] claim to have been inspired by our Lemma 1.2 (i.e., the "sparse case" lemma).
Organization
The (basic) "sparse case" consistency lemma is presented in Section 2. The application to the
PCP Characterization Theorem is presented in Section 3. Section 4 contains a proof of Lemma 1.1
(which refers to sequences of totally independent random points).
Remark: This write-up reports work completed in the Spring of 1994, and announced at the
Weizmann Workshop on Randomness and Computation (January 1995).
2 The Consistency Lemma (for the sparse case)
In this section we present our main result; that is, a combinatorial consistency lemma which refers
to sequences of bounded independence. Specifically, we considered k 2 -long sequences viewed as
k-by-k matrices. To emphasize the combinatorial nature of our lemma and its proof, we adopt
an abstract presentation in which the properties required from the set of matrices are explicitly
stated (as axioms). We comment that the set of all k-by-k matrices over S satisfies these axioms.
A more important case is given in Construction 2.3: It is based on a standard construction of
pairwise-independent sequences (i.e., the matrix is a pairwise-independent sequence of rows, where
each row is a pairwise-independent sequence of elements).
General Notation. For a positive integer k, let [k] kg. For a finite set A, the notation
a 2R A means that a is uniformly selected in A. In case A is a multiset, each element is selected
with probability proportional to its multiplicity.
2.1 The Setting
Let S be some finite set, and let k be an integer. Both S and k are parameters, yet they will be
implicit in all subsequent notations.
Rows and Columns. Let R be a multi-set of sequences of length k over S so that every e 2 S
appears in some sequence of R. For sake of simplicity, think of R as being a set (i.e., each sequence
appears with multiplicity 1). Similarly, let C be another set of sequences (of length k over S). We
neither assume We consider matrices having rows in R and columns in C
(thus, we call the members of R row-sequences, and those in C column-sequences). We denote by
M a multi-set of k-by-k matrices with rows in R and columns in C. Namely,
Axiom 1 For every th row of m is an element of R and the i th column
of m is an element of C.
For every i 2 [k] and -
r 2 R, we denote by M i (-r) the set of matrices (in M) having - r as the i th
row. Similarly, for j 2 [k] and - c 2 C, we denote by M j (-c) the set of matrices (in M) having - c
as the j th column. For every -
we denote by M j
-c) the set of matrices having -
r as the i th row and - c as the j th column (i.e.,
Shifts. We assume that R is "closed" under the shift operator. Namely,
Axiom 2 For every - there exists a unique -
We denote this right-shifted sequence by oe(-r). Similarly, we assume
that there exists a unique - 1. We denote
this left-shifted sequence by oe \Gamma1 (-r). Furthermore 3 , we assume that shifting each of the rows of a
to the same direction, yields a matrix m 0 that is also in M.
We stress that we do not assume that C is "closed" under shifts (in an analogous manner). For
every (positive) integer i, the notations oe i (-r) and oe \Gammai (-r) are defined in the natural way.
Distribution. We now turn to axioms concerning the distribution of rows and columns in a
uniformly chosen matrix. We assume that the rows (and columns) of a uniformly chosen matrix
are uniformly distributed in R (and C, respectively). 4 In addition, we assume that the rows (but
not necessarily the columns) are also pairwise independent. Specifically,
Axiom 3 Let m be uniformly selected in M. Then,
1. For every i 2 [k], the i th column of m is uniformly distributed in C.
2. For every i 2 [k], the i th row of m is uniformly distributed in R.
3. Furthermore, for every j 6= i and - r 2 R, conditioned that the i th row of m equals -
r, the j th
row of m is uniformly distributed over R.
Finally, we assume that the columns in a uniformly chosen matrix containing a specific row-sequence
are distributed identically to uniformly selected columns with the corresponding entry. A formal
statement is indeed in place.
Axiom 4 For every th column in a matrix that is uniformly
selected among those having -
r as its i th row (i.e., m 2R M i (-r)), is uniformly distributed among the
column-sequences that have r j as their i th element.
3 The extra axiom is not really necessary; see remark following the definition of the consistency test.
4 This, in fact, implies Axiom 1.
Clearly, if the j th element of -
differs from the i th element of -
by the above axiom, M j
-c) is not empty. Further-
more, the above axiom implies that (in case r
denotes the set of column-sequences having e as their i th element. (The second equality
is obtained by Axiom 4.)
2.2 The Test
\Gamma be a function assigning matrices in M (which may be a proper subset of all possible k-by-k
matrices over S) values which are k-by-k matrices over some set of values V (i.e.,
The function \Gamma is supposed to be "consistent" (i.e., assign each element, e, of S the same value,
independently of the matrix in which e appears). The purpose of the following test is to check that
this property holds in some approximate sense.
Construction 2.1 (Consistency Test):
1. column test: Select a column-sequence - c uniformly in C, and Select two random
extensions of this column, namely test if the i th column
of \Gamma(m 1 ) equals the j th column of \Gamma(m 2 ).
2. row test (analogous to the column test): Select a row-sequence -
r uniformly in R, and
[k]. Select two random extensions of this row, namely
test if the i th row of \Gamma(m 1 ) equals the j th row of \Gamma(m 2 ).
3. shift test: Select a matrix m uniformly in M and an integer t 2 [k \Gamma 1]. Let m 0 be the matrix
obtained from m by shifting each row by t; namely, the i th row of m 0 is oe t (-r), where -
r denotes
the i th row of m. We test if the first columns of \Gamma(m) match the last columns of
\Gamma(m
The test accepts if all three (sub-)tests succeed.
Remark: Actually, it suffices to use a seemingly weaker test in which the row-test and shift-test
are combined into the following generalized row-test:
Select a row-sequence - r uniformly in R, integers 1g.
Select a random extension of this row and its shift, namely
test if the t)-long suffix of the i th row of \Gamma(m 1 ) equals the
prefix of the j th row of \Gamma(m 2 ).
Our main result asserts that Construction 2.1 is a "good consistency test": Not only that almost
all entries in almost all matrices are assigned in a consistent manner (which would have been
obvious), but all entries in almost all rows of almost all matrices are assigned in a consistent
manner.
Lemma 2.2 Suppose M satisfies Axioms 1-4. Then, for every constant ffi ? 0, there exist a
the consistency test with probability at
least there exists a function - : S 7! V so that, with probability at least 1 \Gamma ffi, the value
assigned by \Gamma to a uniformly chosen matrix matches the values assigned by - to the elements of a
uniformly chosen row in this matrix. Namely,
[k]. The constant ffl does not depend on k and S. Furthermore, it is
polynomially related to ffi .
As a corollary, we get Part (1) of Lemma 1.2. Part (2) follows from Proposition 2.4 (below).
2.3 Proof of Lemma 2.2
As a motivation towards the proof of Lemma 2.2, consider the following mental experiment. Let
be an arbitrary matrix and e be its (i; th entry. First, uniformly select a random matrix,
denoted containing the i th row of m. Next, uniformly select a random matrix, denoted m 2 ,
containing the j th column of m 1 . The claim is that m 2 is uniformly distributed among the matrices
containing the element e. Thus, if \Gamma passes items (1) and (2) in the consistency test then it must
assign consistent values to almost all elements in almost all matrices. Yet, this falls short of even
proving that there exists an assignment which matches all values assigned to the elements of some
row in some matrix. Indeed, consider a function \Gamma which assigns 0 to all elements in the first fflk
columns of each matrix and 1's to all other elements. Clearly, \Gamma passes the row-test with probability
1 and the column-test with probability greater than there is no - so that for a
random matrix the values assigned by \Gamma to some row match - . It is easy to see that the shift-test
takes care of this special counter-example. Furthermore, it may be telling to see what is wrong with
some naive arguments. A main issue these arguments tend to ignore is that for an "adversarial"
choice of \Gamma and a candidate choice of - : S 7! V , we have no handle on the (column) location of
the elements in a random matrix on which - disagrees with \Gamma. The shift-test plays a central role
in getting around this problem; see subsection 2.3.2 and Claim 2.2.14 (below).
Recommendation: The reader may want to skip the proofs of all claims in first reading. We
believe that all the claims are quite believable, and that their proofs (though slightly tedious in
some cases) are quite straightforward. In contrast, we believe that the ideas underlying the proof of
the lemma are to be found in its high level structure; namely, the definitions and the claims made.
Notation: The following notation will be used extensively throughout the proof. For a k-by-k
matrix, m, we denote by row i (m) the i th row of m and by col j (m) the j th column of m. Restating
the conditions of the lemma, we have (from the hypothesis that \Gamma passes the column test)
are uniformly selected in the corresponding sets (i.e., - c2C,
(-c)). Similarly, from the hypothesis that \Gamma passes the row test, we have
It will be convenient to extend the shift
notation to matrices in the obvious manner; namely, oe t (m) is defined as the matrix m 0 satisfying
row From the hypothesis that \Gamma passes the shift-test, we
obtain
Finally, denoting by entry i;j (m) the (i; th entry in the matrix
m, we restate the conclusion of the lemma as follows
Prob i;m (9j so that entry i;j (\Gamma(m)) 6= -(entry i;j
2.3.1 Stable Rows and Columns - Part 1
For each - r 2 R and -
we denote by p - r (-ff) the probability that \Gamma assigns to the row-sequence
r the value-sequence -
namely,
implies that for almost all row-sequences there is a
"typical" sequence of values; see Claim 2.2.3 (below).
Definition 2.2.1 (consensus): The consensus of a row-sequence -
denoted con(-r), is defined
as the value -
ff for which p -
r (-ff) is maximum. Namely,
ff is the (lexicographically first)
value-sequence for which p -
fi)g.
Definition 2.2.2 (stable sequences): Let ffl 2
ffl. We say that the row-sequence -
r is stable if
Otherwise, we say that - r is unstable.
Clearly, almost all row-sequences are stable. That is,
2.2.3 All but at most an ffl 2 fraction of the row-sequence are stable.
proof: For each fixed -
r we have
ff
where (-r). Taking the expectation over -
r 2R R, and using
Eq. (2), we get
r (p max
r
(-ff)g. Using Markov Inequality, we get
and the claim follows. 2
By definition, almost all matrices containing a particular stable row-sequence assign this row-
sequence the same sequence of values (i.e., its consensus value). We say that such matrices are
conforming for this row-sequence.
Definition 2.2.4 (conforming called i-conforming
(or conforming for row-position i) if \Gamma assigns the i th row of m its consensus value; namely, if
row Otherwise, the matrix is called i-non-conforming (or non-conforming
for row-position i).
2.2.5 The probability that for a uniformly chosen i 2 [k] and m 2 M, the matrix m is
i-non-conforming is at most ffl 3
. Furthermore, the bound holds also if we require that the i th
row of m is stable.
proof: The stronger bound (on probability) equals the sum of the probabilities of the following
two events. The first event is that the i th row of the matrix is unstable; whereas the second event
is that the i th row of the matrix is stable and yet the matrix is i-non-conforming. To bound the
probability of the first event (by ffl 2 ), we fix any i 2 [k] and combine Axiom 3 with Claim 2.2.3. To
bound the probability of the second event, we fix any stable - r and use the definition of a stable
row. 2
Remark: Clearly, an analogous treatment can be applied to column-sequences. In the sequel, we
freely refer to the above notions and to the above claims also when discussing column-sequences.
2.3.2 Stable Rows - Part 2 (Shifts)
Now we consider the relation between the consensus of row-sequences and the consensus of their
shifts. By a short shift of the row-sequence - r, we mean any row-sequence - obtained
with 1)g. Our aim is to show that the consensus (as well as stability) is
usually preserved under short shifts.
Definition 2.2.6 (very-stable row): Let ffl
We say that a row-sequence -
r is very stable if it
is stable, and for all but an ffl 4 fraction of d 2 1)g, the row-sequence -
is also stable.
Clearly,
2.2.7 All but at most an ffl 4 fraction of the row-sequence are very-stable.
proof: By a simple counting argument. 2
Definition 2.2.8 (super-stable row): Let ffl
We say that a row-sequence
r is super-stable if it is very-stable, and, for every j 2 [k], the following holds
for all but an ffl 6 fraction of the t 2 [k], the row-sequence - s stable and
con is the j th element of con(-r).
Note that the t th element of oe t\Gammaj (-r) is r . Thus, a row-sequence is super-stable if the
consensus value of each of its elements is preserved under almost all (short) shifts.
2.2.9 All but at most an ffl 6 fraction of the row-sequence are super-stable.
proof: We start by proving that almost all row-sequences and almost all their shifts have approximately
matching statistics, where the statistics vector of -
r 2 R is defined as the k-long sequence
(of
- r (\Delta), so that p j
r (v) is the probability that \Gamma assigns the value v to the j th
element of the row - r. Namely,
(-r). By the definition of consensus, we know that for every stable
row-sequence - r 2 R, we have
its shift
are stable and have approximately matching statistics (i.e., the corresponding
statistics sub-vectors are close) then their consensus must match (i.e., the corresponding
subsequences of the consensus are equal).
subclaim 2.2.9.1: For all but an ffl 5 fraction of the row-sequences -
r, all but an ffl 5 fraction of the shifts
proof of subclaim: Let pref row i;j (m) denote the j-long prefix of row i (m) and suff row i;j (m) its j-long
suffix. By the shift-test (see Eq. (3) and
Prob m;i;d (pref row i;k\Gammad (\Gamma(m)) =suff row i;k\Gammad (\Gamma(m 0 Using Axiom 3 (Part 2) and an averaging
argument, we get that all but a ffl 5 fraction of the - r 2 R, and all but a ffl 5 fraction of d 2 [k \Gamma 1],
Prob i;m (pref row i;k\Gammad (\Gamma(m)) =suff row i;k\Gammad (\Gamma(m 0
We fix such a pair - r and d, thus fixing also
A matrix-pairs (m; m 0 ) for which the equality holds contributes equally to the (appropriate
long portion of the) the statistic vectors of the row-sequences -
r and - s. The contribution of matrix-
pairs for which equality does not hold, to the difference
(v)j, is at most 2
per each relevant j. The subclaim follows. 3
As a corollary we get
2.2.9.2: Let us call a row-sequence, - r, infective if for every j 2 [k] all but an 2ffl 5 fraction
of the t 2 [k] satisfy
all but a 2ffl 5 fraction of the
row-sequences are infective.
proof of subclaim: The proof is obvious but yet confusing. We say that
r is fine1 if for all but an ffl 5
fraction of the d 2 [k] and for every d, we have
oe d (-r)
r is fine1
then for every j there are at most ffl 5 k positions t 2 fj+1; :::; kg so that
oe t\Gammaj (-r) (v)j ? 2ffl 5 .
Similarly, -
r is fine2 if for all but an ffl 5 fraction of the d 2 [k] and for every j ? d we have
oe \Gammad (-r)
(v)j - 2ffl 5 , and whenever - r is fine2 then for every j there are at most ffl 5 k
positions so that
oe \Gammaj+t (-r) (v)j ? 2ffl 5 . Thus, if a row-sequence -
r is
both fine1 and fine2 then for every j 2 [k] all but a 2ffl 1 fraction of the positions t 2 [k] satisfy
oe t\Gammaj (-r) (v)j - 2ffl 5 . By subclaim 2.2.9.1, we get that all but an ffl 5 fraction of the row-
sequences are fine1. A similar statement holds for fine2 (since the shift-test can be rewritten as
selecting setting Combining all these trivialities, the
Clearly, a row-sequence -
r that is both very-stable and infective satisfies, for every j 2 [k] and all
but at most ffl 4 of the t 2 [k], both
and in particular for
It follows that p t
must hold. Thus,
such an -
r is super-stable. Combining the lower bounds given by Claim 2.2.7 and subclaim 2.2.9.2,
the current claim follows (actually, we get a better bound; i.e., ffl 4

Summary

. Before proceeding let us summarize our state of knowledge. The key definitions
regarding row-sequences are of stable, very-stable and super-stable row-sequences (i.e., Defs 2.2.2,
2.2.6, and 2.2.8, respectively). Recall that a stable row-sequence is assigned the same value in
almost all matrices in which it appear. Furthermore, most prefixes (resp., suffices) of a super-stable
row-sequence are assigned the same values in almost all matrices containing these portions (as part
of some row). Regarding matrices, we defined a matrix to be i-conforming if it assigns its i th row
the corresponding consensus value (i.e., it conforms with the consensus of that row-sequence); cf.,
Definitions 2.2.4 and 2.2.1. We have seen that almost all row-sequences are super-stable and that
almost all matrices are conforming for most of their rows. Actually, we will use the latter fact with
respect to columns; that is, almost all matrices are conforming for most columns (cf., Claim 2.2.5
and the remark following it).
2.3.3 Deriving the Conclusion of the Lemma
We are now ready to derive the conclusion of the Lemma. Loosely speaking, we claim that the
function - , defined so that -(e) is the value most frequently assigned (by \Gamma) to e, satisfies Eq. (4).
Actually, we use a slightly different definition for the function - .
Definition 2.2.10 (the function - For a column-sequence - c, we denote by con i (-c) the values that
con(-c) assigns to the i th element in - c. We denote by C i (e) the set of column-sequences having e
as the i th component. Let q e (v) denote the probability that the consensus of a uniformly chosen
column-sequence, containing e, assigns to e the value v. Namely,
so that -(e)
with ties broken arbitrarily.
Assume, on the contrary to our claim, that Eq. (4) does not hold (for this - ). Namely, for a
uniformly chosen the following holds with probability greater that ffi
9j so that entry i;j (\Gamma(m)) 6= -(entry i;j (m)) (5)
The notion of a annoying row-sequence, defined below, plays a central role in our argument. Using
the above (contradiction) hypothesis, we first show that many row-sequences are annoying. Next,
we show that lower bounds on the number of annoying row-sequences translate to lower bounds on
the probability that a uniformly chosen matrix is non-conforming for a uniformly chosen column
position. This yields a contradiction to Claim 2.2.5.
Definition 2.2.11 (row-annoying is said to be
annoying for the row-sequence -
r if the j th element in con(-r) differs from -(r j ). A row-sequence - r is
said to be annoying if - r contains an element that is annoying for it.
Using Claim 2.2.9, we get
2.2.12 Suppose that Eq. (4) does not hold (for -). Then, at least a
fraction
of the row-sequences are both super-stable and annoying.
proof: Axiom 3 (part 2) is extensively used throughout this proof (with no explicit reference).
Combining Eq. (5) and Claim 2.2.9, with probability at least uniformly chosen
satisfies the following
1. there exists a j so that -(entry i;j (m)) is different from entry i;j (\Gamma(m));
2. row i (m) is super-stable;
3. matrix m is i-conforming; i.e., entry i;j (\Gamma(m)) equals con j (row i (m)), for every j 2 [k].
Combining conditions (1) and (3), we get that e = entry i;j (m) is annoying for the i th row of m.
The current claim follows. 2
A key observation is that each stable row-sequence which is annoying yields many matrices which
are non-conforming for the "annoying column position" (i.e., for the column position containing
the element which annoys this row-sequence). Namely,
2.2.13 Suppose that a row-sequence - stable and that r j is annoying for - r.
Then, at least a fraction of the matrices, containing the row-sequence -
r, are non-conforming
for column-position j.
We stress that the row-sequence -
r in the above claim is not necessarily very-stable (let alone super-
stable).
proof: Let us denote by v the value assigned to r j by the consensus of - r (i.e., v
r it follows that v is different from -(r j ). Consider the probability space defined
by uniformly selecting
r is stable it follows that in almost all of these
matrices the value assigned to r j by the matrix equals v. Namely,
(-r). By Axiom 4, the j th column of m is uniformly distributed in
thus we may replace - c 2R C i (r j ) by the j th column of m 2R M i (-r). Now, using the
definition of the function - and the accompanying notations, we get
(-r). The inequality holds since v 6= -(r j ) and by - 's definition
Combining Eq. (6) and (7), we get
and the claim follows. 2
Another key observation is that super-stable row-sequences which are annoying have the property of
"infecting" almost all their shifts with their annoying positions, and thus spreading the "annoyance"
over all column positions. Namely,
2.2.14 Suppose that a row-sequence - r is both super-stable and annoying. In particular,
suppose that the j th element of - annoying for -
r. Then, for all but at most an
ffl 6 fraction of the t 2 [k], the the row-sequence - stable and its t th element (which is
indeed r j ) is annoying for - s.
proof: Since - r is super-stable, we know that for all but an ffl 6 fraction of the t's, con j
and - s is stable (as well), where -
is annoying for -
r, we have
Combining Claims 2.2.12 and 2.2.14, we derive, for almost all positions t 2 [k], a lower bound for
the number of stable row-sequences that are annoyed by their t th element.
2.2.15 Suppose that Eq. (4) does not hold (for -). Then, there exists a set T ' [k] so that
and for every t 2 T there is a set of at least ffi 1
stable row-sequences so that
the t th position is annoying for each of these sequences.
proof: Combining Claims 2.2.12 and 2.2.14, we get that there is a set of super-stable row-
sequences A ' R so that A contains at least a ffi 1 fraction of R, and for every - r 2 A there
exist a j - r 2 [k] so that for all but a ffl 6 of the t 2 [k], the row-sequence -
is stable and
the t th position is annoying for it (i.e., for -
s). By a counting argument it follows that there is a
set T so that jT j - and for every t 2 T at least half of the - r's in A satisfy the above
(i.e., is stable and the t th position is annoying for - s). Fixing such a t 2 T , we consider
the set, denoted A t , containing these - r's; namely, for every -
the row-sequence - s
r (-r)
is stable and the t th position is annoying for it (i.e., for - s). Thus, we have established a mapping
from A t to a set of stable row-sequences which are annoyed by their t th position; specifically, -
r
is mapped to oe t\Gammaj - r (-r). Each row-sequence in the range of this mapping has at most k preimages
(corresponding to the k possible shifts which maintain its t th element). Recalling that A t contains
at least ffi 1\Delta jRj sequences, we conclude that the mapping's range must contain at least ffi 1
sequences, and the claim follows. 2
Combining Claims 2.2.15 and 2.2.13, we get a lower bound on the number of matrices which are
non-conforming for the j th column, 8j 2 T (where T is as in Claim 2.2.15). Namely,
be as guaranteed by Claim 2.2.15 and suppose that j 2 T . Then, at least a
1fraction of the matrices are non-conforming for column-position j.
proof: By Claim 2.2.15, there are at least ffi 1
stable row-sequences that are annoyed by
th position. Out of these row-sequences, we consider a subset, denoted A, containing exactly
row-sequences. By Claim 2.2.13, for each -
r 2 A, at least a fraction of the matrices
containing the row-sequence - r are non-conforming for column-position j. We claim that almost all
of these matrices do not contain another row-sequence in A (here we use the fact that A isn't too
large); this will allow us to add-up the matrices guaranteed by each - r 2 A without worrying about
multiple counting. Namely,
subclaim 2.2.16.1: For every - r 2 R
proof of subclaim: By Axiom 3 (part 3), we get that for every i 0 6= i the i 0 -th row of m 2R M i (-r) is
uniformly distributed in R. Thus, for every i 0
(-r). The subclaim follows. 3
Using the subclaim, we conclude that for each -
r 2 A, at least a fraction of
the matrices containing the row-sequence - r are non-conforming for column-position j and do not
contain any other row-sequence in A. The desired lower bound now follows. Namely, let B denote
the set of matrices which are non-conforming for column-position j, let B
denote the set of matrices in B i (-r) which do not contain any row in A except for the i th row;
then
The claim follows. 2
The combination of Claims 2.2.15 and 2.2.16, yields that a uniformly chosen matrix is non-conforming
for a uniformly chosen column position with probability at least (1 1. For
a suitable choice of constants (e.g., yields contradiction to Claim 2.2.5. Thus,
Eq. (4) must hold for - as defined in Def. 2.2.10, and the lemma follows.
2.4 A Construction that Satisfies the Axioms
Clearly, the set of all k-by-k matrices over S satisfies Axioms 1-4. A more interesting and useful
set of matrices is defined as follows.
Construction 2.3 (basic construction): We associate the set S with a finite field and suppose
Furthermore, [k] is associated with k elements of the field so that 1 is the multiplicative
unit and i 2 [k] is the sum of i such units. Let M be the set of matrices defined by four field
elements as follows. The matrix associated with the quadruple (x; has the (i; th entry
Remark: The column-sequences correspond to the standard pairwise-independent sequences fr
Similarly, the row-sequences are expressed as fr
Proposition 2.4 The Basic Construction satisfies Axioms 1-4.
proof: Axioms 1 is obvious from the above remark. The right-shift of the sequence fr+js
is To prove that Axiom 3 holds, we rewrite the i th
row as fs
are pairwise independent and uniformly distributed
in S \Theta S which corresponds to the set of row-sequences. It remains to prove that Axiom 4 holds.
We start by proving the following.
Fact 2.4.1: Consider any i; j 2 [k] and two sequences -
that r
proof of fact: By the construction, there exists a unique pair (a; b) 2 S \Theta S so that a
every (existence is obvious and uniqueness follows by considering any two equations; e.g.,
Similarly, there exist a unique pair (ff; fi) so that ff
every We get a system of four linear equations in x; x
This system has rank 3 and thus jSj solutions, each defining a matrix
in M j
Using Fact 2.4.1, Axiom 4 follows since
jS \Theta Sj
and so does the proposition.
3 A Stronger Consistency Test and the PCP Application
To prove Lemma 1.3, we need a slightly stronger consistency test than the one analyzed in
Lemma 2.2. This new test is given access to three related oracles, each supplying assignments
to certain classes of sequences over S, and is supposed to establish the consistency of these oracles
with one function - : S 7! V . Specifically, one oracle assigns values to k 2 -long sequences viewed as
two-dimensional arrays (as before). The other two oracles assign values to k 3 -long sequences viewed
as 3-dimensional arrays, whose slices (along a specific coordinate) correspond to the 2-dimensional
arrays of the first oracle. Using Lemma 2.2 (and the auxiliary oracles) we will present a test which
verifies that the first oracle is consistent in an even stronger sense than established in Lemma 2.2.
Namely, not only that all entries in almost all rows of almost all 2-dimensional arrays are
assigned in a consistent manner, but all entries in almost all 2-dimensional arrays are assigned
in a consistent manner.
3.1 The Setting
Let S, k, R, C and M be as in the previous section. We now consider a family, M c
, of k-by-k
matrices with entries is C. The family M c
will satisfy Axioms 1-4 of the previous section. In
addition, its induced multi-set of row-sequences, denoted R, will correspond to the multi-set M;
namely, each row of a matrix in M c
will form a matrix in M (i.e., the sequence of elements of C
corresponding to a row in a M c
-matrix will correspond to a M-matrix). Put formally,
Axiom 5 For every
and every i 2 [k], there exists so that for every j 2 [k],
the (i; th entry of m equals the j th column of m (i.e., entry i;j equivalently,
row m). Furthermore, this matrix m is unique.
Analogously, we consider also a family, M r
, of k-by-k matrices the entries of which are elements in
R so that the rows 5 of each
correspond to matrices in M.
3.2 The Test
As before, \Gamma is a function assigning (k-by-k) matrices in M values which are k-by-k matrices over
some set of values V (i.e.,
) be (the supossedly corresponding)
function assigning k-by-k matrices over C (resp., R) values which are k-by-k matrices over V
Construction 3.1 (Extended Consistency Test):
1. consistency for sequences: Apply the consistency test of Construction 2.1 to \Gamma c
. Same for \Gamma r
2. correspondence test: Uniformly select a matrix
and a row i 2 [k], and compare the i th
row in \Gamma c
(m) to \Gamma(m), where is the matrix formed by the C-elements in the i th row
of m. Same for \Gamma r
The test accepts if both (sub-)tests succeed.
Lemma 3.2 Suppose M;M c
satisfy Axioms 1-5. Then, for every constant fl ? 0, there exist
a constant ffl so that if a function (together with some functions \Gamma c
passes the extended consistency test with probability at least 1 there
exists a function - : S 7! V so that, with probability at least 1 \Gamma fl, the value assigned by \Gamma to a
uniformly chosen matrix matches the values assigned by - to each of the elements of m.
Namely,
Probm
M. The constant ffl does not depend on k and S. Furthermore, it is polynomially
related to fl.
The proof of the lemma starts by applying Lemma 2.2 to derive assignments to C (resp., R) which
are consistent with \Gamma c
on almost all rows of almost all k 3 -dimensional arrays (ie., M c
and M r
, respectively). It proceeds by applying a degenerate argument of the kind applied in the
proof of Lemma 2.2. Again, the reader may want to skip the proofs of all claims in first reading.
3.3 Proof of Lemma 3.2
We start by considering item (1) in the Extended Consistency Test. By Lemma 2.2, there exists
a function - c
so that the value assigned by \Gamma c
), to a
uniformly chosen row in a uniformly chosen matrix M c
matches with high probability
the values assigned by - c
) to each of the C-elements (resp., R-elements) appearing in this
5 Alternatively, one can consider a family, M r
, of k-by-k matrices the entries of which are elements in R so that the
columns of each
correspond to matrices in M. However, this would require to modify the basic consistency
test (of Construction 2.1), for these matrices, so that it shifts columns instead of rows.
row. Here "with high probability" means with probability at least 1 \Gamma ffi, where ffi ? 0 is a constant,
related to ffl as specified by Lemma 2.2. Namely,
(entry i;j
3.3.1 Perfect Matrices and Typical Sequences
Eq.
Our next step is to relate - c
to \Gamma. This is done
easily by referring to item (2) in the Extended Consistency Test. Specifically, it follows that the
value assigned by \Gamma, to a uniformly chosen matrix m 2 M, matches, with high probability, the
values assigned by - c
) to each of the columns (resp., rows) of m. That is
Definition 3.2.1 (perfect matrices): A matrix m 2 M is called perfect (for columns) if for every
th column of \Gamma(m) equals the value assigned by - c
to the j th column of m
(i.e.,
called perfect (for rows) if row i
(row i (m)), for every i 2 [k].
(perfect
(c) All but a ffi 1 fraction of the matrices in M are perfect for columns.
(r) All but a ffi 1 fraction of the matrices in M are perfect for rows.
proof: By the Correspondence (sub)Test, with probability at least 1 \Gamma ffl, a uniformly chosen row
in a uniformly chosen
is "given" the same values by \Gamma c
and by \Gamma (i.e., row i (\Gamma c
for On the other hand, by Eq. (8), with probability at least 1 \Gamma ffi,
a uniformly chosen row in a uniformly chosen
is "given" the same values by \Gamma c
and by
(i.e., entry i;j (\Gamma c
(entry i;j (m)), for i 2R [k] and all j 2 [k]). Thus, with probability
at least 1 uniformly chosen row in a uniformly chosen
is "given" the same
values by \Gamma and by - c
(i.e.,
(entry i;j (m)), for i 2R [k] and all j 2 [k]). Using
regarding M c
) and the "furthermore" part of Axiom 5, we get part (c) of the
claim (i.e., col j
similar argument holds for part (r). 2
A perfect (for columns) matrix "forces" all its columns to satisfy some property \Pi (specifically, the
value assigned by - c
to its column-sequences must match the value \Gamma of the matrix). Recall that
we have just shown that almost all matrices are perfect and thus force all their columns to satisfy
some property \Pi. Using a counting argument, one can show that all but at most a 1
fraction of
the column-sequences must satisfy \Pi in almost all matrices in which they appear. Namely,
Definition 3.2.3 (typical sequences): Let
We say that the column-sequence - c (resp.,
row-sequence - r) is typical if
(-c). Otherwise, we say that - c is non-typical.
3.2.4 All but at most an
fraction of the column-sequence (resp., row-sequences) are
typical.
We will only use the bound for the fraction of typical row-sequences.
proof: We mimic part of the counting argument of Claim 2.2.16. Let N be a set of non-typical
row-sequences, containing exactly
sequences. Fix any - r 2 N and consider the set of matrices
containing - r. By Axiom 3 (part 3 - regarding M), at most a ffi 2fraction of these matrices contain
some other row in N . On the other hand, by definition (of non-typical row-sequence), at least a
fraction of the matrices containing - r, have \Gamma disagree with - r
(-r) on -
r, and thus are non-perfect (for
rows). It follows that at least a ffi 2fraction of the matrices containing - r are non-perfect (for rows)
and contain no other row in N . Combining the bounds obtained for all -
r 2 N , we get that at least
a 2fraction of the matrices are not perfect (for rows). This contradicts Claim 3.2.2(r), and so
the current claim follows (for row-sequences and similarly for column-sequences). 2
3.3.2 Deriving the Conclusion of the Lemma
We are now ready to derive the conclusion of the Lemma. Loosely speaking, we claim that the
function - , defined so that -(e) is the value most frequently assigned by - c
to e, satisfies the claim
of the lemma.
Definition 3.2.5 (the function -
(-c) i denote the value assigned by - c
to the i th element of
denotes the set of column-sequences having e as
the i th component). We consider - so that -(e) ties
broken arbitrarily.
The proof that - satisfies the claim of Lemma 3.2 is a simplified version of the proof of Lemma 2.2. 6
We assume, on the contrary to our claim, that, for a uniformly chosen
Probm
so that entry i;j (\Gamma(m)) 6= -(entry i;j (m))
As in the proof of Lemma 2.2, we define a notion of an annoying row-sequence. Using the above
(contradiction) hypothesis, we first show that many row-sequences are annoying. Next, we show
that lower bounds on the number of annoying row-sequences translate to lower bounds on the
probability that a uniformly chosen matrix is non-perfect (for columns). This yields a contradiction
to Claim 3.2.2(c).
Definition 3.2.6 (a new definition of annoying rows): A row-sequence -
is said to be
annoying if there exists a j 2 [k] so that the j th element in - r
(-r) differs from -(r j ).
Using Claim 3.2.2(r), we get
3.2.7 Suppose that Eq. (9) hold and let
. Then, at least a
k fraction of the
row-sequences are annoying.
6 The reader may wonder how it is possible that a simpler proof yields a stronger result; as the claim concerning
the current - is stronger. The answer is that the current - is defined based on a more restricted function over C and
there are also stronger restrictions on \Gamma. Both restrictions are due to facts that we have inferred using Lemma 2.2
proof: Combining Eq. (9) and Claim 3.2.2(r), we get that with probability at least
a uniformly chosen matrix is perfect for rows and contains some entry, denoted (i; j), for
which the \Gamma value is different from the - value (i.e., entry i;j (\Gamma(m)) 6= -(entry i;j (m))). Since the
-value of all rows of m matches the \Gamma value, it follows that the i th row of m is annoying. Thus,
at least a fl 1 fraction of the matrices contain an annoying row-sequence. Using Axiom 3 (part 2 -
regarding M), we conclude that the fraction of annoying row-sequences must be as claimed. 2
A key observation is that each row-sequence that is both typical and annoying yields many matrices
which are non-perfect for columns. Namely,
Suppose that a row-sequence -
r is both typical and annoying. Then, at least a
fraction of the matrices, containing the row-sequence - r, are non-perfect for columns.
is annoying, there exists a j 2 [k] so that the the j th component of
(-r) (which is the value assigned to r j ) is different from -(r j ). Let us denote by v the value - r
assigns to r j . Note that v 6= -(r j ). Consider the probability space defined by uniformly selecting
r is typical it follows that in almost all of these matrices the value
assigned to r j by the \Gamma equals v; namely,
By Axiom 4 (regarding M), the j th column of m is uniformly distributed in C i (r j ). Now, using
the definition of the function - and the accompanying notations, we get
The inequality holds since v 6= -(r j ) and by - 's definition q r j
Combining Eq. (10)
and (11), we get
Prob i;m (entry i;j (\Gamma(m)) 6=- c
and the claim follows. 2
Combining Claims 3.2.7, 3.2.4 and 3.2.8, we get a lower bound on the number of matrices which
are non-perfect for columns. Namely,
Suppose that Eq. (9) hold and let
2. Then, at least a fl 2fraction of the
matrices are non-perfect for columns.
proof: By Claims 3.2.7 and 3.2.4, at least a
fraction of the row-sequences are
both annoying and typical. Let us consider a set of exactly
\Delta jRj such row-sequences, denoted
A. Mimicking again the counting argument part of Claim 2.2.16, we bound, for each -
r 2 A, the
fraction of non-perfect (for columns) matrices which contain - r but no other row-sequence in A.
Using an adequate setting of ffi 2 and fl 2 , this fraction is at least 1. Summing the bounds achieved
for all -
r 2 A, the claim follows. 2
Using a suitable choice of fl (as a function of ffl), Claim 3.2.9 contradicts Claim 3.2.2(c), and so
Eq. (9) can not hold. The lemma follows.
3.4 Application to Low-Degree Testing
Again, the set of all k-by-k-by-k arrays over S satisfies Axioms 1-5. A more useful set of 3-
dimensional arrays is defined as follows.
Construction 3.3 (main construction): Let M be as in the Basic Construction (i.e., Construction
2.3). We let M c
be the set of matrices defined by applying the Basic Construction
to the element-set Specifically, a matrix in M c
is defined by the quadruple (x;
where each of the four elements is a pair over S, so that the (i; th entry in the matrix equals
are viewed as two-dimensional vectors over the finite field S
and are scalars in S. The (i; th entry is a pair over S which represents a pairwise independent
sequence (which equals an element in
Clearly,
3.4 Construction 3.3 satisfies Assuptions 1-5.
Combining all the above with the low-degree test of [GLRSW, RS96] using the results claimed
there 7 , we get a low-degree test which is sufficiently efficient to be used in the proof of the PCP-
Characterization of NP.
Construction 3.5 (Low Degree Test): Let f : F n 7! F , where F is a field of prime cardinality,
and d be an integer so that jF j ? 4(d
and M r
be as in Construction 3.3, with
be
auxiliary tables (which should contain the corresponding f-values). The low degree test consists of
1. Applying the Extended Consistency Test
7!
2. Selecting uniformly a matrix m 2 M and testing that the Polynomial Interpolation Condition
(cf., [GLRSW]) holds for each row; namely, we test that
for all
3. Select uniformly a matrix in M and test matching of random entry to f . Namely, select
uniformly check if entry i;j
The test accepts if and only if all the above three sub-tests accept.
Proposition 3.6 Let f : F n 7! F , where F is a field, and let ' j. Then, the Low
Degree Test of Construction 3.5 requires O(') randomness and query length, poly(') answer length
and satisfies:
completeness: If f is a degree-d polynomial, then there exist
and
so that the test always accepts.
7 Rather than using much stronger results obtained via a more complicated analysis, as in [ALMSS], which rely
on the Lemma of [AS].
soundness: For every there exists an ffl ? 0 so that for every f which is at distance
at least ffi from any degree-d polynomial and for every
and
, the test rejects with probability at least ffl. Furthermore, the constant ffl is a
polynomial in ffi which does not depend on n; d and F .
As a corollary, we get Lemma 1.3.
proof: As usual, the completeness clause is easy to establish. We thus turn to the soundness
requirement. By Claim 3.4, we may apply Lemma 3.2 to the first sub-test and infer that either the
first sub-test fails with some constant probability (say ffl 1 ) or there exists a function - : F n 7! F so
that with very high constant probability (say
entry i;j
holds for all On the other hand, by [GLRSW] (see also [S95, Thm 3.3] and
[RS96, Thm 5]), either
or - is very close (specifically at distance at most 1=(d polynomial. A key
observation is that the Main Construction (i.e., Construction 3.3) has the property that rows in
are distributed identically to the distribution in Eq. (13). Thus, for every j 2 [k] either
or - is at distance at most ffi 2
some degree-d polynomial. However, we claim
that in case Eq. (14) holds, the second sub-test will reject with constant probability. The claim
is proven by first considering copies of the GLRSW Test (i.e., the test in Eq. (14)).
Using Chebishev's Inequality and the hypothesis by which each copy rejects with probability at
least 1=2(d we conclude that the probability that none of these copies rejects is bounded
above by 2(d+2) 2
1. Thus, the second sub-test must reject with probability at least ffl 2
accounts for the substitution of the - values by the entries in \Gamma(\Delta). We conclude that -
must be -close to a degree-d polynomial or else the test rejects with too high probability (i.e.,
Finally, we claim that if f disagrees with - on of the inputs then the third sub-test
rejects with probability at least ffl 3
the distance from f to - is bounded by the sum
of the distances of f to the matrix and of - to the matrix). The proposition follows using some
arithmetics: Specifically, we set Lemma 3.2), and verify
that
4 Proof of Lemma 1.1
There should be an easier and direct way of proving Lemma 1.1. However, having proven Lemma 2.2,
we can apply it 8 to derive a short proof of Lemma 1.1. To this end we view '-multisets over S
8 This is indeed an over-kill. For example, we can avoid all complications regarding shifts (in the proof of
Lemma 2.2).
as k-by-k matrices, where
'. Recall that the resulting set of matrices satisfies Axioms 1-4.
Thus, by Lemma 2.2, in case the test accepts with probability at least 1 \Gamma ffl, there exists a function
such that
is the set of all k-multisets over S and E l (A) is the set of all l-multisets extending A. We
can think of this probability space as first selecting B 2R S k 2
and next selecting a k-subset A in
B. Thus,
where denotes the set of all k-multisets contained in B. This implies
as otherwise Eq. (15) is violated. (The probability that a random k-subset hits a subset of densityk
is at least 1.) The lemma follows.
A previous version of this paper [GS96] has stated a stronger version of Lemma 1.1, where the
sequences F are claimed to be identical (rather than different on
at most k locations), for a fraction of all possible Unfortunately, the proof
given there was not correct - a mistake in the concluding lines of the proof of Claim 4.2.9 was
found by Madhu Sudan. Still we conjecture that the stronger version holds as well, and that it can
be established by a test which examines two random 1)-extensions of a random k-subset.

Acknowledgment

We are grateful to Madhu Sudan for pointing out an error in an earlier version, and for other helpful
comments.



--R

Proof Verification and Intractability of Approximation Problems.
Probabilistic Checkable Proofs: A New Characterization of NP.
Transparent Proofs and Limits to Approximation.

Checking Computations in Polylogarithmic Time.
Hiding Instances in Multioracle Queries.
Free Bits
Efficient Probabilistically Checkable Proofs and Applications to Approximation.
Improved Non-Approximability Results


Approximating Clique is almost NP-complete
On the Power of Multi-Prover Interactive Pro- tocols
Some Improvement to Total Degree Tests.

A Taxonomy of Proof Systems.
Proofs that Yield Nothing but their Validity or All Languages in NP Have Zero-Knowledge Proof Systems
A Combinatorial Consistency Lemma with application to proving the PCP Theorem.
The Knowledge Complexity of Interactive Proof Systems.
Clique is Hard to Approximate within n 1
Fully Parallelized Multi Prover Protocols for NEXP-time
Algebraic Methods for Interactive Proof Systems.

Testing Polynomial Functions Efficiently and over Rational Domains.
Robust Characterization of Polynomials with Application to Program Testing.

Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems.
--TR

--CTR
Eli Ben-Sasson , Oded Goldreich , Prahladh Harsha , Madhu Sudan , Salil Vadhan, Robust pcps of proximity, shorter pcps and applications to coding, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Eli Ben-Sasson , Madhu Sudan, Robust locally testable codes and products of codes, Random Structures & Algorithms, v.28 n.4, p.387-402, July 2006
parallelization of probabilistic proof systems;probabilistically checkable proofs PCP;low-degree tests