BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR93-1387
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Robust Characterizations of Polynomials and Their Applications to 
        Program Testing
AUTHOR:: Rubinfeld, Ronitt 
AUTHOR:: Sudan, Madhu
DATE:: September 1993
PAGES:: 24
ABSTRACT::
The study of self-testing and self-correcting programs leads to the search 
for robust characterizations of functions. Here we make this notion precise 
and show such a characterization for polynomials. From this characterization, 
we get the following three applications: First, we can construct simple and 
efficient self-testers for polynomial functions. Secondly, it provides results 
in the area of coding theory, by giving extremely fast and efficient 
error-detecting schemes for some well known codes. Thirdly, this 
error-detection scheme plays a crucial role in recent results on hardness of 
approximating some NP-optimization problems.
END:: CORNELLCS//TR93-1387
BODY::
Robust Characterizations of Polynomials
and
Their Applications to Program Testing*
Ronitt Rubinfeld**
Madhu Sudan***
TR 93-1387
September 1993
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
This paper unifies and extends part of the results contained in Gemmell et al.
[GLRSW91] and Rubinfeld and Sudan [RS92].
**Cornell University. email: ronitt?cs.cornell.edu This work is supported by ONR
Young Investigator grant N00014-93-1-0590 and the United States-Israel Binational
Science Foundation. Part of this work was done while the author was at Princeton
University, supported by DIMACS (Center for Discrete Mathematics and Theoretical
Computer Science), NSF-STC88-09648.
***l.B.M. Thomas J. Watson Research Center. email: madhu?watson.ibm.com. Part
of this work was done when the author was a student at the University of California at
Berkeley under the support of NSF PYl Grant CCR 8896202.
R?obust Characterizations of Polynomials and Their
Applications to Program Testing *
R,onitt R?ubinfe1d tMadliu Sudan
Abstract
The study of self-testing and self-correcting programs leads to the search for robust
characterizations of functions. Here we make this notion precise and show such a
characterization for polynomials. From this characterization, we get the following three
applications: First, we can construct simple and efficient self-testers for polynomial
functions. Secondly, it provides results in the area of coding theory, by giving extremely
fast and efficient error-detecting schemes for some well known codes. Thirdly, this error-
detection scheme plays a crucial role in recent results on hardness of approximating
some NP-optimization problems.
*This paper unifies and extends part of the results contained in Gemmell et al. [GLRSW9l] and Rubinfeld
and Sudan [RS92].
?Cornell University. email: roniff?cs.cornell.edu. This work is supported by ONR Young Investigator
grant N00014-93-1-0590 and the United States - Israel Binational Science Foundation. Part of this work was
done while the author was at Princeton University, supported by DIMACS (Center for Discrete Mathematics
and Theoretical Computer Science), NSF-STC88-09648.
tI.B.M. Thomas J. Watson Research Center. email: madhu?watson.ibm,com. Part of this work was done
when the author was a student at the University of California at Berkeley under the support of NSF PYI
Grant CCR 8896202.
1 Introduction
The study of program checkers [Blu88] [BK89], self-testing programs [BLR9O] and self-correcting
programs [BLR?90] [Lip91] was introduced in order to allow one to use a program P to com-
pute a function without trusting that P works correctly. A program checker checks that the
program gives the correct answer on a particular input, a se1f-test?ng program for f tests that
program P is correct on most inputs, and a self-correct?ng program for f takes a program
P that is correct on most inputs and uses it to compute f correctly on every input with
high probability. The program checker, self-tester and self-corrector may call the program
as a black box, are required to do something other than to actually compute the function,
and should be much simpler and at least different than any program for the function f in
the precise sense defined by [BK89j. It is straightforward to show that checkers, self-testers
and self-correctors for functions are related in the following way: If f has a self-tester and
a self-corrector, then it can be shown that f has a program result checker. Conversely, if f
has a checker, then it has a self-tester (though not necessarily a self-corrector).
The above approach was suggested as an alternative to program verification. Though this
approach involves a certain amount of work that must be done at each program call, this
approach has several advantages. One big advantage is that rather than just checking the
correctness of the program code, this approach checks that the implementation of the program
(the compiled program code running on the given hardware) gives a correct answer. In
addition, in program verification, every program written for a function f needs to be verified,
whereas only one checker, self-tester and self-corrector need be designed for each specific
function f. This approach allows one to use programs while they are being developed and
undergoing change, even when the user does not have access to the code.
One of the main goals of the research in the area of self-testing/correcting programs and
program checking is to find general techniques for finding very simple and efficient self-testers,
self-correctors and checkers for large classes of problems, In fact, some success towards this
goal has been achieved. For example, in [BK89], it is shown how to use techniques from the
area of interactive proof systems in order to write checkers. Using these and other techniques,
checkers (and hence self-testers) have been found for a variety of problems [AHK, BK89,
Rub90, Kan9O, BFLS91, BF9l]. If a function is random self-reducible (essentially that the
value of the function at any input can be inferred from its value at randomly chosen inputs)
then it has a self-corrector [BLR9Oj [Lip91]. This provides self-correctors for a surprising
range of functions, including the class of linear functions (homomorphisms between groups)
and polynomials.
In the direction of characterizing functions that have self-testers, some success has been
achieved in [BLR9o]. They give a number of methods of constructing self-testers for func-
tions, some of which we mention here: They observe that any checker for a function can
be used to construct a self-tester for the function. They present a particular method of
constructing self-testers for a variety of functions based on a method of bootstrapping from
tests over smaller domains. They also show another method of constructing self-testers for
all linear functions, i.e., functions which act as homomorphisms between groups (or satisfy
f(x) t f(y) = f(x t y) for any group operation t).
2
The main focus of this paper is to study and understand functions that have self-testers, and
to broaden the class of functions that have self-testers. The linearity tester of [BLR9O] is
the starting point for this paper. A particularly interesting feature of this linearity tester is
that it breaks the task of self-testing a function into the two tasks of (1) testing it for certain
"structural properties" and (2) using the structural property to then identify the function
precisely. In this paper we introduce a new notion --H a function family tester --H which helps
delineate these two tasks more clearly. We first introduce some terminology:
We work with functions defined over some finite domain D. The distance between two
functions f and g over the domain D is fraction of points x ? D where the two functions
disagree:
d(f, ??			I?x?Df(x)#g(x)1I
DI
We say that two functions are e-close if d(f, g) ? e. Sometimes, we drop the e from the
word and just describe two functions as being close. In such cases, it is implied that we are
talking of some small c, say 1%. In terms of this notion a self-tester for a function f may be
defined as follows:
A self-tester T for a function f over a domain D, is a (randomized) oracle program that
takes as input a program P and behaves as follows:
o+ Accepts P if d(P, f) = 0.
o+ Rejects P (with high probability) if P and f are not close.
o+ Behaves arbitrarily otherwise.
Testers for function families using robust characterizations Let ? be a family of
functions. A function family teste? T for the family ?, takes as input a program P and tests
if there exists a function f c ? such that P is close to f.
The notion of a function family tester captures the notion of verifying properties of a function
as follows: Let ? be a property we wish to test for. Let ? be the family of all functions that
have the property ?. Then a function family tester for ? can be used to test if a program
P "essentially" has the property ? (i.e. that exists a function with property ? that is close
to P.) To concretize some of these abstract definitions, let us work with the simple example
of the property of linearity among functions mapping from Z? to Zp. For this example, the
family of functions we work with is ?inear = ?faIa ? Zp, fa(x) = a x). Thus a tester
for the family of linear functions verifies that the computation of a program P is essentially
linear.
The existence of a function family tester for any class of functions implies a powerful charac-
terization of the family. In particular, consider any program that is rejected by the tester. In
order to reject the program, the tester will have found some evidence in the small set of sam-
pled points which "proves" that P can not be a member of ?. In other words, all members of
? must satisfy some property on the set of inputs which are examined by the family tester.
Thus all members of F satisfy a "local" property (by local we mean a property on a set of
3
small size). Moreover, if all such local properties are satisfied, then the tester accepts the
function, implying that these local constraints form a characterization of the family. Thus in
order for a function family to have a tester, it needs to have a local characterization. In our
example, such a local characterization of linear functions is the property that Vx, y ? Zp,
f(x) t f(y) = f(x t y). If a function is not linear then there exists a counterexample of
size three which proves that it is not linear. In general, we define a local characterization as
follows:
Let D be a domain and let f map elements of D into ?. A k-local property is
a function ? : x ?)k fo, 1J. We say that f has property ? on the tuple
(x1,... ,xk) c Dk if P evaluates to ion the tuple (x1,f(x1),... ,xk,f(xk)).
A k-local characterization of a function family ? on D consists of a k-local prop-
erty ? on D and a collection of neighborhoods Af c Dk, such that f ? ? if and
only if f has property? on every neighbourhood in Af
Local characterizations do not form a sufficient condition for the constructions of testers.
Typically an exact local characterization of a family of functions involves universal quantifi-
cation which is not easy to verify. In our example, the characterization of linear functions
by. the property Vx, y ? Z?, f(x) t f(y) = f(x t y) is not useful since we cannot hope
to efficiently test that this holds for all possible pairs x, y. Thus for a characterization to
be useful for testing, it needs to be "robust", involving the words "for most" rather than
"for all" Somewhat more formally, we call a local characterization robust, if we have the
following property:
If the fraction of neighborhoods N E on which a function f has property ?
is at least 1 --H 6, then the there exists a function g ? ?, such that f and 9 are
&close.
Our results on function family testing One of the main emphases of this paper is
to find robust characterizations for the family of low degree univariate and multivariate
polynomials. In Section 3 we start by describing some (well-known) local characterizations of
univariate and multivariate polyonomials and then prove that some of these characterizations
are actually robust characterizations. As an immediate consequence we get function family
testers for all low-degree polynomials over finite fields. For the case of polynomials over Zp,
our testers are very simple and do not even need to multiply elements of the field. Our
testers are the first testers which directly attempt to test the total degree of a polynomial
(as opposed to the testers of [BFLS9l, FGLSS9l, AS92], all of which test that the degree in
each variable is not too large). The proof of correctness of our tester also is different from the
proofs of correctness of the other testers in that it does not rely on an inductive argument
based on the number of variables. This allows for its "efficiency" to be independent of the
number of variables and provides the hope for the existence of a tester with nearly optimal
efficiency.
In the second phase of this paper we introduce the notion of test sets which allows us to use
the results on function family testing to obtain self-testers for specific functions. Informally,
4
a test set is a set of points from the domain, such that no two functions from the family
F agree with each other on all the points from the test set. Our self-tester for a specific
function f would require, as a description of f, its value on all points in a test set. The
complexity (running time) of the self-tester will depend on the size of the test set.
Other implications of low-degree testing The task of constructing family testers for
the family of low-degree polynomials is closely related to the task of error-detection in ?eed
Solomon codes. In fact, a low-degree test can be described as a "randomized" error-detector
which determines if the number of errors in a received word is small or not. In this sense, the
error-detectors we construct have the feature that they are highly efficient and can be used
to get estimates on the distance of a received word from a valid codeword. This perspective
can similarly be applied to the results of [BLR9O] to get randomized error-detecting and
correcting schemes for the Hadamard codes, which probe the received word in only a constant
number of bits to detect an error or find any bit of the codeword closest to the received word.
In fact, it has been shown by M. Naor [Nao92] that these results can be used to construct
codes for which error-detection/correction can be performed by uniform quasi-polynomial
sized circuits of constant depth.
A different perspective on the construction of family testers is to view it as the following
approximation problem:
Given a family of functions ? and a function P, estimate the distance d(P, ?)
between P and ? to within a small additive error.
A tester for a function family ? essentially yields such an approximator (provided d(P, ?)
is smaller than half) by defining some new quantities ?(P, ?) which are easy to estimate by
random sampling and then showing that some approximate relations hold between ?(P, ?)
and d(P, F). For example, the linearity test of [BLR9O] may be viewed as trying to ap-
proximate the distance d(f, ?hnear) To approximate this distance they define the quantity
?(L ?linear) Pr[f(x) t f(y) $ f(x t ?)j which is easy to approximate. Then they show
that &(L ?inear)/3 < d(f, ?inear) < 26(f, ?linear) The testers given here define similar
quantities related to low-degree polynomials and show similar approximate identities. These
approximate identities may be of independent interest.
The low-degree tester given here is also related to the multilinearity test in [BFL91J, which is
a central ingredient in their proof of MIP NEXPTIME. The tester given here provides an
alternate mechanism which works in their setting. The efficiency of a low-degree test becomes
very important to the ensuing results on hardness of approximations [FGLSS9l, ALMSS92]
and therefore a lot of attention has been paid to this problem [BFL91, BFLS91, FGLSS91,
AS92J. The tester given here is particularly well-suited to such multiple prover applications
and provides a one round constant prover proof that a function is a low degree polynomial
over finite fields. (This is observed in [ALMSS92j (see also [Sud921) and follows by using an
improved analysis for Lemma 11 from [AS92].) This turns out to play a crucial role in the
NP = PCP(logn, 0(1)) result of [ALMSS92], which in turn provides hardness results for a
wide variety of approximation problems.
5
Organization of Paper The rest of this paper is organized as follows. In Section 2 we
formally define the notions of local characterizations - exact and robust. Section 3 lists some
(well-known) exact characterizations of low-degree polynomials. Sections 4 and 5 show that
two of these exact characterizations are robust. In Section 6 we describe the applications
of these characterizations to self-testing of programs. Finally in Section 7 we describe some
other applications of these testers and list some open issues.
2 Local Characterizations: Exact and Robust
In this section we make precise the notion of a local characterization and what we mean
by exact and robust characterizations. We will also isolate a parameter associated with
the robust characterizations which captures the efficiency of the tester suggested by the
characterization.
We will use D to represent a finite domain. We will consider here, families of functions ?
where f Ei ? maps elements from D to a range ?. We illustrate these definitions using the
example of linear functions. llere the domain and range are Zp and the family of functions
is ?j??ja ? Zp where fa(X) = a xl.
Definition 1 (Neighborhoods) A k-local neighborhood N is an ordered tuple of (not nec-
essarily distinct) k points from D . A k-local collection of neighborhoods d\f is a set of k-local
neigborhoods.
Definition 2 (Properties) A k-localproperty ? is afunctionfrom (D x ?)k to fo, 1). We
say that a function f satisfies a property ? over a neighborhood N if?(?(x, f(x))l:??) = 1
Definition 3 (Exact Characterizations) A property P over a collection of neighborhoods
AT is an exact characterization of a family of functions ? if any function f satisfies ? over
all neighborhoods N c AT if and only if f Ei ?. The characterization is k-local if the property
? (and the collection AT) is k-local.
In our example, the collection of neighborhoods AT = ?(x, y, x + y) x, y c 2?1. The property
? is 3-local and is satisfied by f on the triple (x1, x2, x3) if f(x1) + f(x2) = f(x3). Thus over
the collection of neighborhoods AT, ? gives a 3-local characterization of the family of linear
functions.
Definition 4 (Robust Characterizations) A property ? over a collection of neighbor-
hoods AT is said to be a ?-robust characterization ?, if f satisfies ? on all but ? fraction
of the neighborhoods in AT only if f is 1/4-close 1 to some function g El ?. Moreover, all
1The exact constant determining closeness is not very important for the family of multivariate polynomi-
als. For most of the characterizations we consider here, it can be shown that any function f is ((1 + o(1))6)-
close to some member g of ? if f is 1/4-close to g and violates only 6-fraction of the neighborhood constraints.
6
members of ? satisfy ? on all neighborhoods in M. The parameter 61 is referred to as the
efficiency of the characterization. 2
To continue with the example of linear functions, we could now apply the theorem of [BLR9o]
to say that ? over the neighborhood AT is a (2/9 --H e)-robust characterization of linear
functions (for any e> 0).
3 Exact Characterizations of Polynomials
In this section we start by describing some (well-known) exact local characterizations of
polynomial functions. In later sections we will show that some of these characterizations can
be made robust.
The family of degree d polynomials can be characterized in a number of ways. The differ-
ent characterizations arise from looking at different collections of neighborhoods AT. The
property P typically remains invariant in the following sense: P will be satisfied by f on
a neighborhood N if there exists a polynomial which agrees with f on all points in N.
The complexity of a neighborhood test, i.e., testing whether a constraint is being satisfied
by a neighborhood, is also influenced by the choice of the neighborhood. Thus by choos-
ing the characterizations appropriately, we might be able to tradeoff the simplicity of the
neighborhood test against the number of times the test needs to be repeated. The different
characterizations also have to be qualified by different restrictions on the underlying ring.
For instance, some characterizations hold only for finite fields while others hold only for rings
of the form Zm. We will take care to point out the restrictions on the characterizations. We
give examples of possible neighborhoods and their corresponding tests.
1. Univariate polynomials
The following characterization of univariate polynomials holds for a function f mapping
from a ring 1? to R.
(a)
Characterization: f : R ?` J? is a polynomial of degree at most d if and only
if ....... , Xd?+1 ? I?, there exists a polynomial 9?O?d+1 such that f(xt)
gxoxd+1(X%)
Neighborhood structure: AT 1?d+2, i.e., all possible (mulii)-subsets of R of size
d+2.
Complexity of neighborhood test: A test of the above nature involves finding
the (unique) degree d polynomial g which agrees with f at the points ?..... , Xd
and then evaluating :g(xd+1) and verifying that this equals f(xd+1). Standard
interpolation techniques (see, for instance, [dW7O]) imply that this is equivalent
2In order to test if f is close to some member of ?, one would need to sample at least ? of the
neighborhoods in At and test if ? holds on these neighborhoods. Hence ? represents the efficiency of
the characterization.
7
to computing coefficients ...... , ?d??1, where the t?%Y'5 depend only on the txil's,
and verifying that Z%%461 oi?f(xi) 0. The Q'5 can be computed using elementary
algorithms with 0(d3) additions, subtractions and multiplications over R.
2. Univariate polynomials using evenly spaced points
This characterization works over the ring Zm and the field Zp. Let ?? = (d$I)(?i
The interpolation identity for degree d polynomials on evenly spaced points, x, x +
..... , x + (d +1). h, reduces to zt--H%? Qf(x + i h) = 0. ?Ve refer to x as the starting
point and h as the offset.
(a)
Characterization: f : Zm Zm is a polynomial of degree at most d if and only
ffVx,h? im, Zt?%1?f(x+i?h) =0.
Neighborhood structure: Define the neighborhood sets Nx,h = fx+i?hJdi=%I Then
the neighborhood collection is Af = Ux,hEZ Nx,?.
Complexity of Neighborhood Test: Notice that the constants ?? are now indepen-
dent of x and h and can be precomputed once and for all. In fact, due to the
special relationship between the Q'5, given the value of f at the points x + i
we can compute the above summation with 0(d2) additions and subtractions and
no multiplications (see appendix).
3. Multivariate polynomials using lines
This characterization applies to m-variate functions over a finite field F Define the
notion of a line through the space F? as follows: For x, h ? pm, the line 1x,h through
x with offset h is the set of points tx + i h i E; FJ. We will often refer to the line in
its parametric form lX,h(?) Observe that a polynomial f of total degree d, restricted
to a line lx,h(?) becomes a univariate polynomial of degree at most d in the parameter
i. This gives us the following characterization of degree d polynomials over sufficiently
large finite fields (pj > 2d+ 1). 3
(a)
Characterization: The function f : pm , F is a polynomial of degree at most d
if and only if Vx, h ? pm, f restricted to li,h(?) is a univariate polynomial in i of
degree at most d (see appendix for a proof).
Neighborhood Structure: Let the neighborhoods be lines. Then AW = UjEF lx,h(?)
Complexity of Neighborhood Test: In this form the characterization is not very
local since the counterexamples are lines, i.e., collections of ?F points. But this
characterization is interesting to us because it says that the characterization of
multivariate polynomials can be reduced to the characterization of univariate
polynomials (on these lines). Thus we find that we can now use, for instance,
3Observe that the above characterization does not appear strong enough in its requirement of the param-
eter IFI. Indeed, for the case of fields of prime order this can be improved to the optimal case IF > d+2 and
this has been shown recently by Katalin Friedi [Fri93]. It is tempting to conjecture that Fl > d + 2 is a suffi-
cient condition for this characterization to hold. Surprisingly enough, this is not the case; A counterexample
to this effect is also shown by Friedl.
8
Characterization 1 to find counterexamples of size at most d. The complexity of a
neighborhood test here is no more than the complexity of the neighborhood test
in Characterization 1.
4. Multivariate polynornials Using axis parallel lines
This characterization is a specialization of the charaterization above, in terms of special
lines - axis pa?allel lines. We say that a line is axis parallel if the offset It contains only
one non-zero coordinate.
(a)
Characterization: f : ? F is a polynomial of degree at most d in each variable
if and only if v axis parallel lines, f restricted to the line is a univariate polynomial
of degree at most d. Notice that here we characterize polynomials differently, i.e.,
in terms of individual degree in each variable rather than total degree.
(b) Neighborhood Structure: The neighborhoods here are sets of the form N?,pj
t(Pi,. ,P%?1,t,?j+1,. ,Pm)It ? F?, for every choice 0fPj ? F, and every choice
of i ? ?1, . . . ,ml. Then ? U%E?1m),P,EF
(c) Complexity of Neighborhood Test: The complexity of a neighborhood test is the
same as the complexity of Characterization 1.
5. Multivariate polynornials: evenly spaced points
A combination of Characterizations 2 and 3 gives the following characterization of
polynomials over Zp, for p> nid.
(a) Characterization: f: Zp? " Zp is a polynomial of degree at most d if and only if
vx,h?z?m, Zffi%?f(x + ih) = 0, where ? =
(b) Neighborhood Structure: The neighborhoods here are of the form Nx,h = ?x +
ihji ? .0,..., d + 11) Then AT =--H Ux,hEZ? N?,h.
(c) Complexity of Neighborhood Test: The complexity of this neighborhood test is
the same as the complexity in Characterization 2.
6. Multivariate polynornials: evenly spaced points - 2
This characterization is a trivial consequence of the characterization above, and seems
weaker since its neighborhood structure is larger than those of the ones above. But it
turns out that this characterization is much more useful due to the kind of robustness
it yields. This characterization holds for polynomials over Zp, for p> max?md, lOdi.
(a) Characterization: f : zr 2p is a polynomial of degree at most d if and only
if Vx, It ? Z7, the values of fat the points ?x + iIt i ? ?o,. . ., 1041 agree with
some univariate polynomial g of degree at most d in t.
(b) Neighborhood Structure: The neighborhoods here are sets of the form Nx,h
?x + iItIi ? .0...,, 10d11. Then AT =--H UX,hEZp Nx,h
9
(c)
Complexity of the neighborhood test: Once again it turns out that the complexity
of this test is within a constant factor of the complexity of the test in Charac-
terization 2, i.e., 0(d2) additions and subtractions and no multiplications (see
appendix).
All characterizations above turn out to be robust. The robustness of Characterization 1 is
straightforward and omitted here (see, for instance, [Sud92J). The robustness of 4 follows
from the work of [BFL91J (see also [BFLS91, FGLSS91, AS92, Lun92J). Robustuess of 2, 3,
5 and 6 are presented in this section.
A typical robust characterization theorem for degree d polynomials in ni variables over a
finite field F would go as follows:
There exists a 6o (which may be a function of d, m, F?) such that for ? ? ?, if
the fraction of neighborhoods where P satisfies the local constraints is at least
1 --H ?, then P is &close to some degree d polynomial (where ? is some function of
6).
An important parameter in determining the efficiency of a tester, is the relationship between
6o and m, d, El. For instance, if 6o dnilo1gjF , then this implies that we will have to test
that the local property holds for at least dm log jF randomly chosen neighborhoods before
we can satisfy ourselves that F is close to some polynomial. Our main thrust will be to get
a theorem which holds for as high a 6o as possible. ?
In what follows, we show first that Characterization 5 above is robust with 6o 0(d'2) This
proof gives a simple and efficient tester for the family of multivariate polynomials which
works with 0(d3) probes into f. Robustness of the characterizations in 2 and 3 follow as
special cases. This bound on 6o is in contrast to the robustness of 4 which has an inherent
dependency on m.
Next we show a robustness of Characterization 6. The efficiency of this test is analysed
modulo the efficiency of a certain test for bivariate polynomials and is shown to be within a
constant factor of the bivariate test. We also show that the efficiency of the bivariate test is
0(d), giving a test for multivariate polynomials which works with 0(d2) probes into f.
4 A Robust Characterization of Polynomial Punctions
In this section, we prove the robustness of Characterization 5. We consider a function
(program) P mapping m variables from Zp to Zp and prove the following:
4A secondary parameter of interest is the relationship between t and 6. In all the proofs that follow, we
will only show that E = 26. Actually, once such a result is shown it can be shown again that any E > 6 works.
10
Theorem 5 Let 6o = O( (d%)2 If P : z?m " Zp satisfies
6=
d+1
Pr P(x) # ZQP(x+i.h)
X,hERZp			i?1
6o
then there ewists a degree d polynomial 9 : z?m , ? which is 26-close to P
This theorem makes very minimal requirements on the field size required for its validity. The
theorem is valid whenever Characterization 5 holds and Friedi [Fri93j has shown that this
holds for p > d + 2 - the smallest concievable field size for which the test could be defined.
We do not know of other testers which work with such a minimal requirement on the field
size.
We define g(x) to be ???h?zp?tZ?H QP(x + ih)i, where maj of a set is the function that
picks the element occuring most often (choosing arbitrarily in the case of ties). The rest of
this section is devoted to showing that 9 is a low-degree polynomial. But first we show that
9 is 26-close to P
Lemma 6 g and P agree on more than 1 --H 26 fraction of the inputs from Zp?
Proof: Consider the set of elements x such that Pr?[P(x) = zd+l Q?P(x + i * h)] ?
1/2. If the fraction of such elements is more than 26 then it contradicts the condition that
Prx,?[Z?ffi%1 ?P(x + i * h) = 0] = 6. For all remaining elements, P(x) = g(x). ?
In the following lemmas, we show that the function g satisfies the interpolation formula for
all x, h and is therefore a degree d polynomial. We do this by first showing that for all x,
g(x) is equal to the interpolation of P at x by most offsets t. We then use this to show that
the interpolation formula is satisfied by 9 for all x, h.
Lemma 7 For all x C z?m, Pr?[g(x) =zd+l??p(x+i*h)] > l--H2(d+1)6.
Proof: Observe that h1, h2 ?R z?m implies
x + i * h1 ?R z?m and x +j*h2?RZp?
d+1
? Pr [P(x + i * h1) = ? ?P(x + i * h1 + j * h2)] > 1 --H 6
h1,h2			j=1
?Y?r2[P(X+i*h2) = ?%P(x+i*h1+j*h2)] >1--H6
i--Hi
Combining the two we get
Pr?1,?2 [Zffi' ??P(x + i * h1) = ??ffi4 zffiN Q?P(x + i * h1 + j * h2)
= Z?$i'?F(x+j * h2)]
11
> 1--H2(d+1)6
The lemma now follows from the observation that the probability that the same object is
drawn twice from a set in two independent trials lower bounds the probability of drawing the
most likely object in one trial: Suppose the objects are ordered so that p? is the probability
of drawing object i, and Pi > P2 > ... Then the probability of drawing the same object
twice is ZiP2 <Z.PiPt. = Pi ?
Lemma 8 For all x, h c z?m, if 6 ? 2(d$2y' then Zd+i ?.g(x + i * h) = 0 (and thus 9 is a
degree d polynomial [dW7o$).
Proof: Observe that, since h1 + ih2 ?R z?m, we have for all 0 ? i ? d + 1
d+i
hY,hTh [g(x + i * h) = ? o??P((x + i * h) + j * (hi + ih2))] > 1 --H 2(d + 1)6
j--H--Hi
Furthermore, we have for all 1 ? j ? d + 1
d+i
Pr [Z?P((x+j*hi)+i*(h+j*h2))=0]>1--H6
h1,h2 i=O
Putting these two together we get
d+i			d+i d+i
Pr [??g(x+i*h) = ??Z?P((x+j *hi)+i* (h+j *h2)) = 0] >0
h1,h2 i=O			j=i			i--H--HO
The lemma follows since the statement in the lemma is independent of hi, h2, and therefore
if its probability is positive, it must be 1. ?
Proof (of Theorem 5): Theorem 5 follows from Lenimas 6 and 8 ?
5 Efficient tester for polynomials
In this section we prove the robustness of Characterization 6. Recall that this charac-
terization uses the collection of neighbourhoods AT = tN?,h x, h ? where Nx,h =
x ...... , x + lOdh). The following theorem shows that the efficiency of this charac-
terization is 0(d), i.e., if a function satisfies the consistency test on all but a 0(di) fraction
of the neighbourhoods then it is close to a polynomial.
Theorem 9 There exists a constant c such that for 0 ? 6 < %, if f is a function from Z;%
to Zp which satisfies the neighborhood consistency test on all but a 6 fraction of the collection
of neighborhoods AT = ?Nx,?Ix, h ? z?m? (where N?,h = tx, x ...... , x + lodhi), then there
exists a polynomial g : z?m Zp of total degree at most d such that d(f,g) < (1 + o(1))6
(provided md =
12
In the rest of this section we prove this theorem. Fix a function f which satisfies the
neighborhood constraints on all but a ? fraction of the neighborhoods.
The proof follows the same basic outline as the one in Section 4, but in order to achieve
the better efficiency, we use ideas that can be thought of in terms of error-correction. Thus
many of the steps that were quite simple in Section 4 require more work here. In Section 4
the function 9 was defined to be the value that occurs most often (for most h) when one
looks at the evaluation at x of the unique polynomial which agrees with the values of f at
x+h,...,x+(d+ 1)h. Here we view the values ofa polynomial at x+h,...,x+ lOdh as a
code word. Intuitively, the values of f at x + ??..., x + 1Odh will often have enough good
information in it to allow us to get back to a correct codeword. The function 9 defined below
can be thought of as the value that occurs most often (for most h) when one looks at the
polynomial defined by the e?or co?ection of the values of f at x + ??..., x + lOdh evaluated
at x. We then show that g has the following properties:
1. g(x) = f(x) with probability at least 1 --H --H o(?) if x is picked randomly from z?m.
2. On every neighbourhood N?,h, 9 is described by a univariate polynomial of degree d.
Notice that Characterization 6 now implies that 9 is a degree d polynomial.
Definition 10 Fof x, h ? z?m, we define Px,h(i) to be (the unique) polynomial in i which
satisfies Px,h(i) = f(x + ih) for at least 6d values of?. ? ?O,..., 1Od?. If no such polynomial
exists then Px,h is defined to be error.
Define 9: Z7 Z? to be 9(x) =--H plurahty?fPx,h(O)?
where the plurality is taken over P's which are not error.
In Section 4 it is shown that if one computes the value of a polynomial function at x by
interpolating from the values of the function along offset hi which in turn are computed by
interpolating from the values of the function along offset h2, then one would get the same
answer as if one had computed the value of the function at x by interpolating from the values
of the function along offset h2 which in turn are computed by interpolating from the values of
the function along offset h1. This is not hard to see because it turns out that an interpolation
is a weighted summation and obtaining the identity amounts to changing the order of a
double summation (see for instance Lemma 7). Here 9 is actually an interpolation of the
erroncorrection of the values of the function, which is no longer a simple algebraic function
of the observed values. We repair the situation by constructing a bivariate polynomial Q(i, j)
which agrees with f(x + i h1 + j h2) for most values of i and j. This allows us to get back
to simple interpolation where we work with the function Q(i,j) rather than f. Lemma 11
shows when such a bivariate polynomial can be set up to agree with a matrix of values m??.
Lemma 12 shows how to use this polynomial to simulate the effect of the interchange in the
order of the summation.
13
Lemma 11 There exists a constant c > 0 such that if X, Y c 2? with X			= 6d and
if ?riYt?x and IQijEY are univariate (degree d) polynomiaTh which satisfu:
o+ For all i E X, r?(j) $ cj(i) for at most 5 fractions of the j's.
o+ For all j ? Y, r?(j) $ cj(i) for at most 5 fractions of the i's.
Then there exists a polynomial Q(.,.) such that for all i,j Q(i,j) = r?(j) = cj(i)
Proof: Let c > 4. Call a point (i,j) bad if r?(j) $ %(i). Let X' be a subset of X of size
d +1. Observe that the number of bad points in the rows indexed by X'is at most
Thus there must exist at least 2d columns Y' such that there are no bad points in X' >c
(since 6(d;i) ? 2d). There must exist a bivariate polynomial Q(i, j) of degree d in i and j
which agrees with r?(j) and cj(i) for all (i,j) E X' x Y'. But if Q(i,j) agrees with cj(i) at
d +1 places, then it must agree with cj at all places. Thus for all j c Y' Q(i,j) = cj(i).
We now show that for all i E X, r? agrees with Q(i,.). Fix the row i. The number of bad
points on this row is at most 6c But Q agrees with r?(j) on all good points in the columns
indexed by Y', and there are at least d + 1 of these. Thus Q and r agree on the ith row. A
similar argument can now be used to show that Q agrees with c on the jth column. ?
Lemma 12 (Matrix Polynomial Lemma) There exists a constant c1 such that givenfam-
ilies of univariate degree d polynomials ?r?ylOd and ?%1J%? io,io ? .0,..., lodi and a matrix
?mij1tffiodo,ji9yo which satisfies:
o+ For 90% of the i's, r?(j) = m?? for 1 --H Wd fraction of the 5's (including 5 = So).
o+ For 90% of the 5's, c5(i) = m?? for 1 --H m')? fraction of the i's (including i = i0).
Then there exists a bivariate polynomial Q(i,j) which satisfies:
o+ For at least 60% of the i's in ?0,..., 10d?, Q(i,j0) =
o+ For at least 60% ofthej's in ?0,...,10dJ, Q(i0,j) =
Proof: Let c' > 230C (where c is as in Lemma 11). Let X be the set of rows of A' with
the property that rj(5) equals cj(i) for all but td of the values of 5 c ?0,..., 10d?, where
the agreement also holds for 5 = So Observe that since the total number of bad points (i.e.,
points where either m?? $ r?U) or m?? $ Q(i)) is less than 2??2,the fraction of such rows
is at most 60%. Similarly let Y be the set of good columns. It can now be seen that the
conditions of Lemma 11 are now applicable, implying that there exists a polynomial Q(i, 5)
such that Q(i,5) = r?(5) = c?(i) for all (i,j) ? X x Y. Moreover due to the agreement at
= i0 and 5 = So. we have QY.5o) = m??0 for all i c X and similarly Q(i0,j) = m?0? for all
5?Y			?
14
The following lemmas are analogous to Lemmas 6, 7 and 8 of Section 4. Lemma 13 and
Corollary 14 roughly correspond to Lemma 7. Lemma 13 essentially states that the plurality
in the definition of 9 is actually an overwhelming majority. This may be obtained by setting
i0 = 0 is the statement of the lemma. The slightly stronger statement used here is needed
later. Lemma 15 is similar to Lemma 6 and shows that g and f agree at all but a 6 + o(6)
fraction of the places. Lemma 17 shows that 9 is a multivariate polynomial of degree d.
Lemma 13 There exists a constant c1 such that for 6i = c16, the following holds:
Vx c prn,i0 ? ?0,. . . , 10d), Pr [P?,h,(io) = P???i0h1,h2(0)] > 1 --H
h1,h2
Proof: Pick h1, h2 ?R 2p? and define M = (m?? to be the matrix given by ??j =
f(x + ih1 + jh2). We show that M satisfies the conditions required by Lemma 12 (with
jo = 0), with probability at least 1 --H 6?. This suffices to prove the lemma since this implies
that the polynomial Px,h1 is the polynomial Q(i,j) restricted to j = 0 and that Rz+?0h1,h2 is
Q(i0,j). Thus Px,hi(?o) = Px+i0h1,h2(0) = Q(i0,0).
Any row of the matrix, other than the 0th row, represents a random neighborhood (inde-
pendent of x) and satisfies the neighborhood constraint with probability 1 --H 6. Thus with
probability at least 1 --H 106 we have that the fraction of rows that don't have a degree d
polynomial describing them is at most .9. Similarly for the columns. Thus M satisfies the
conditions required by Lemma 12 with probability at least 1 --H 206. Substituting c1 = 20
is the statement of the lemma finishes the proof. (Notice that M actually satisfIes much
stronger conditions, namely, a majority of the rows (columns) are in exact agreement with
some polynomial - rather than just being close to a polynomial, which is what is required by
the lemma.) E]
Corollary 14 For xc z?m, i c ?0,. . ., 10d1, Pr? [g(x + ih) = Px?(i)1 > 1 --H 26?.
Proof: Let B be the set of h's which violate P?,h(i) = maj0flty?1 fPx+ih,h1 (0)1. For all
h ? B notice that g(x + ih) = Px,h(i). Also for h in B, the probability that for a randomly
chosen h1 that Px+ih,h1 (0) $ Px,h(i) is at least 1/2. Thus with probability at least 27I?
we find that a randomly chosen pair of h, hi, violate the condition Px+ih,h1(O) =
Applying Lemma 13 we get that IB is at most 26?. ?
p
We next show that g and f agree in most places:
Lemma 15 d(f,g) <6(1 +o(1))
Proof: Let R' be the set of x's which satisfy f(x) $ Px,h(0) for at least 26? fraction of the
h's in z?m. Observe that due to Corollary 14, for all x ? B', f(x) is the same as g(x) (g(x)
can disagree with P?,h(O) on at most 26i fraction of the h's.) The size of B' as a fraction of
zm be at most ? Thus we find that d(f,g) < = 6(1 + o(1)). ?
can			____
15
Definition 16 Fo? x, h c z?m, we define P?(?,?)(i) to be (the unique) polynomial in i which
satisfies Px,h(?) = g(x + ih) for at least 6d values of i ? to,..., 10d?. If no such polynomial
exists then ?x?9,h? is defined to be error
Lemma 17 There exists a constant c such that if ? < % then Vx, h g(x) =
Proof: As in the proof of Lemma 13 we will pick a convenient matrix on which we will
apply Lemma 12. This time the matrix of choice is obtained by picking h1, h2 CR z?m and
letting m? = g(x + ih+j(h1 +ih2)).
We will now show that Lemma 12 can be applied to this matrix with high probability (for
= Jo = 0). Observe that every row tmijlJ% represents a random neighborhood containing
the fixed point x + ih and hence Corollary 14 implies that ?x+ih,h1 +?h2 (J) agrees with m??
for any choice of j with probability 1 --H 26?. Thus, for every i, with probability at least
1 --H (1 + c)2?, Px+ih,h1+ih2(I) agrees with niij for all but 1c fraction of the j's and this
agreement holds for j = 0. Thus with probability at least 1 --H (1 + c)2061, this holds for
at least 90% of the rows. By picking c = 0(d1)? notice that this satisfies the conditions
required of the rows in Lemma 12. A similar argument based on the columns shows that
the conditions required of the columns are also true with probability 1 --H (1 + c)2061 --H
(All columns except for the 0th one represent random neighborhoods.) Thus the conditions
required for Lemma 12 are satisfied with probability at least 1 --H 40(1 + c)6i --H
Applying Lemma 12 we find that there exists a bivariate polynomial Q(i,j) such that it
agrees with m?0 for 60% of the i's. Moreover, ?oj = Q(0,j) for 60% of the j's, implying
Fx,h1(J) = Q(0,j). But, with probability 1 --H 26?, (from Corollary 14) pJ9) (0) --H g(x)
implying g(x) = Q(0, 0). This implies that g(x) lies on the same degree d polynomial in i
which agrees with g(x+ih) for at least 6d values of i from to,..., lOdi. Thus g(x) =
with probability at least 1 --H 40(2 + c)&i. But since this statement is independent of h1 and
h2, its probability, if positive, must be 1. ?
Proof (of Theorem 9): Lemma 17 implies that along each line 1xh, 9 can be described
by a univariate polynomial of degree at most d. Characterization 6 can now be applied to
infer that 9 is a polynomial of total degree at most d. From Lemma 15 we now know that f
and 9 differ in at most ?(1 + o(1)) fraction of the places. This completes the proof. E]
6 Self-Testing Polynomials
In this section we complement the results of [BF90] [Lip91] by showing how to construct a
self-tester for any polynomial function. The results can also be generalized to give self-testers
and self-correctors for functions in finite dimensional function spaces that are closed under
shifting and scaling.
Previously, program testing was thought of as the following: pick a randorn input x and verify
that P(x) = f(x) by cornputing f via another program. This method has two problems: first,
16
it relies on believing the other program to be correct, and secondly, since testing is often
done at runtime [BLR90], it negates the benefits of designing faster programs, since the
computation time will be dominated by the computation time of the old
As in [BLR90J, our testers are of a nontraditional form and use the robust characterization
of the function being tested: the tester is given a short specification of the function in the
form of properties that the function must have, and verifies that these properties "usually"
hold. We show that these properties are such that if the program "usually" satisfies these
properties, then it is essentially computing the correct function.
Test Sets Given that a function computes a polynomial, we want a way of specifying that
it is the correct polynomial. We do this by specifying the function value of the polynomial at
a number of inputs. It is easy to see that the number of inputs required is exactly the number
of inputs necessary to determine whether two degree d polynomials are distinct. Since any
two degree d univariate polynomial functions can only agree on d points, it suffices to check
whether or not the polynomial functions agree at any d t 1 points to determine whether or
not they are distinct. On the other hand, distinct multivariate polynomials can agree at an
unbounded number of points. However, it is well known that there exists a set of (d + 1)?
points such that no two degree d, m-variate polynomials can agree at all points in the set.
We make the following definition:
Definition 18 We say that T f(x1,y1),... , (xt, yt)1 is a (d, m)-polynomial test set if
there is only one degree d, m variabTh polynornial f such that for all i ? [1,..., t], f(Xi) =
A (d, m)-test set need only be of size (d + l)?
When the number of variables is small, the provision that the value of the function is known
on at least (d+ 1)rn points is not very restrictive since the degree is assumed to be small with
respect to the size of the field: Suppose one has a program for the R?SA function x3 mod p.
Traditional testing requires that the tester know the value of f(x) for random values of x.
Here one only needs to know the following simple and easy to generate specification: f is a
degree 3 polynomial in one variable, and f(O) = o,f(1) = 1,f(--H1) = --H1,f(2) = 8. These
function values are the same over any field of size at least 9.
6.1 Testing Algorithm
Our self-tester for a polynomial of degree d with rn variables assumes that the specification
of the polynomial is given by the value of the function on a (d, m)-polynomial test set.
Theorem 19 If f is a degree d polynomial in m variables over Zp, and the value of f is
given on a (d, m)-polynomial test set, then for e < O(1/d2), f has an (2(7+2)' 4e)-self-tester
on Zp with O((d + 1)m/e + d max(d2, 1E)) calls to P.
17
The self-testing is done in two phases, one verifying that the program is essentially computing
some degree d polynomial function g, and the other verifying that the g is the correct
polynomial function by verifying that 9 (rather than P) is correct on the polynomial test
set.
We now give the self-testing program which is used to prove Theorem 19.
For simplicity, in the description of our self-testing program, we assume that whenever the
self-tester makes a call to P, it verifles that the answer returned by P is in the proper range,
and if the answer is not in the proper range, then the program notes that there is an error.
We use X ?R Z? to denote that xis chosen uniformly at random in z?m
program Polynornial-Self-Test(F,e, ?, ? ((x1, f(x1)),... , (xt, f(xt))))
Degree Test
Repeat O(??1l0g(1/P)) times
Pick x,t ?R z?m and test that zd+1?F(x ti*h 0
Reject P if the test fails more than an e fraction of the time.
Equality Test
for j going from 1 to t do
Repeat O(log(d/,3)) times
Pick t ?R z?m and test that f(xj) ?d+1??P(xj +i*
Reject p if the test fails more than 1/4th of the time.
6.2 Correctness of Algorithm
Let ? = Prx,t[z?%+? QP(x 4- i * t) $ 0]
Definition 20 We say pw?ram P is e-900d if ? E andVj c ?o,...,d1, Prt[f(x?)
--H2
?td+10LP(x?+i*t)] >3/4. We sayP ise-badifeither?> 2e or if?j such thatPrt[f(x?) =
Ztd+1 ?P(x?+i*t)] ? 1/2 (Note that there are progranis which are neithere-good ore-bad).
The following lemma is easy to prove
Lemma 21 With probability at least 1 --H an e-good program is passed by Polynomial-Self-
Test. With probability at least 1 --H an e-bad program is rejected by Polynomial-Self-Test.
It is easy to see that if a program P 2??+2??c0mPute5 f, then it is e-good. On the other
hand, we need to show that if P does not 4e-compute f then it is e-bad. We show the
contrapositive, i.e. that if P is not e-bad, then it 4&computes f
18
If P is not &bad, then ? ? 26. Under this assumption, we show that there exists a function
9 with the following properties:
1.			g(x)			P(x) for most x.
2. Vx, t ?d+1 ??g(x + it) 0, and thus 9 is a degree d polynoinial.
3.			g(xj)			f(xj) forj c
The function 9 is as defined in the previous section on robust characterizations, and properties
(1) and (2) follow from the lemmas proved there. In order to show property (3), we also
have:
Lemma 22 9(Xj) f(xj)
Proof: Follows from the definition of 9 and the fact that P is not &bad.
Theorem 23 The program Polynomial-Self-Test is a (2(d%2)? 4e) -self-testing program for
any degree d polynomial function over z?m specified by its values at any (d, m)-polynomial
test set I, if e < 4(d$2)2
Proof: Follows from Lemmas 21,8, and 22. E]
7 Conclusions
Comparison with other low degree tests. In [BFL9l][Lun92], there is a test, which in
our setting allows the self-tester to be convinced that the program is computing a multivariate
polynomial function of low degree in polynomial time. However, the tests are somewhat
complicated to perform, because they involve the reconstruction of a univariate polynomial
given its values at a number of points (which in turn requires multiplications and matrix
inversions), and later the evaluation of the reconstructed polynomial at random points. If
the number of variables in the original multivariate polynomial is relatively small, this is as
difficult as computing the polynomial function from scratch, and therefore is not different
than the program in the sense defined by [BLR?90J, and does not give a self-tester or checker.
Relationship with proof checking. The low-degree tester forms a crucial ingredient in
the recent results on proof checking. Our result from Section 4 gives a very simple proof of
the one of the relatively hard parts of the proof of MIP--H--HNEXPTIME shown by [BFL9lj.
The hardness of the proof of the tester of [BFL9l] (and its simplifications, see for instance,
[FGLSS9l]) is in their need to rely on the isoperimetric properties of the m-dimensional grid.
Our proof on the other hand does not seem to require any combinatorics, and is instead
based on elementary algebraic/probabilistic techniques. This difference may be explained
19
as follows: The success of the test does indeed depend on the isoperimetric properties of a
graph related to the neighborhood structure. In the case of the test of [BFL91] this graph
turns out to be in the m-dimensional grid. In our case, the underlying graph turns out to
be a complete graph. This graph is obviously much easier to analyse for its properties and
hence the proof is devoid of any combinatorial statements.
Application to other testers The tester given in Section 5 can be interpreted in a
more general fashion as a technique to relate the efficiency of a certain bivariate test to the
efficiency of a related multivariate test. We describe this connection somewhat loosely here:
Let T be a test for univariate polynomials. Let B be the test for bivariate
polynomials which picks an axis and an axis parallel line at random and runs
T 011 this line. Let M be a multivariate test which pick a random line in the
m-dimensional space and runs T on this line. Notice that the tests B and M
are completely specified once T is specified. Then for a wide class of tests T, the
efficiency of M is at most a constant times the efficiency of B.
This connection plays a crucial role in the PCP(logn, 1) NP result of [ALMSS92J. ? They
use a result of [AS92j who consider a test arising out of Characterization 1: Pick a random
set of d + 2 points and verify that f restricted to these d + 2 points behave as a degree
d polynomial. [AS92] show that the efficiency of the corresponding bivariate test is 0(1).
[ALMSS92] use this in conjuction with the connection described here to show that the related
multivariate test has efficiency 0(1).
Some open questions It can be seen that the Theorem 9 can be made stronger if the
Lemma 11 can be strengthened as follows:
Conjecture 24 Let I, J be any subsets of F, and let frit??i and f????j be families of
univariate polynomials which satisfy
o+ Vi c I, for all but k values of I c J, r?(j)
o+ Vj c J, for all but k values of i c I, r?(j) cj(i).
ThenVi?1,VjEi J?rj(j)=Q(i), provided I,IJ >2k+2d+2.
Lemma 11 of the appendix shows this property if I, J > O(kd). The best result in this
direction is due to Arora and Safra [AS92] who prove such a property for I, J > 2k+O(d2).
llowever, the conjecture as stated above remains open and if resolved positively would yield
the following, which we state as a separate conjecture:
5(ALMSS92] use the resulting tester in the form of a single round constant prover proof system for verifying
low-degree of oracles. This gives the first single round constant prover proof system for membership in NP
languages, where the prover is a polynomial sized oracle. Other proof systems with such properties are
known today [BGLR93], but these inherit this property from the proof system of [ALMSS92].
20
Conjecture 25 For the evenly spaced neighborhood ?
Zp"' 1? the efficiency of the following test is 0(1): "Pick a
test that f restricted to this neighborhood agrees with some
i(x,x+h,...,xtlodh)x,h E
random neighborhood in AT and
degree d polynomial"
A positive resolution of Conjecture 24 would also find applications in the area of transparent
proofs [BFLS91, Bab93] by allowing for transformations of proofs into "extremely trans-
parent" ones (using the methods of [AS92, ALMSS92]) where the blowup incurrred in the
transformation would be only slightly super-linear.
8 Acknowledgments
We are very grateful to Avi Wigderson for suggesting that our tester in Section 4 can be
made more efficient, as well as his technical help in proving the theorems of Section 5. We
are also very grateful to Sasha Shen for pointing out that the tester given in [GLRSW91]
works for multivariate polynomials. In particular, Characterization 3 and its relevance to
our test are due to him. We are grateful to Dick Lipton for interesting conversations on the
use of the testers presented here, and to Mike Luby, Shafi Goldwasser and Umesh Vazirani
for technical suggestions.
References
[AliK] L. Adleman, M. Huang, and K. Kompella. Efficient checkers for number-
theoretic computations. Submitted to Information and Computation.
[ALMSS92]
[AS92]
[Bab93]
[BF90]
5. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification
and the intractability of approximation problems. In Proceedings of the 33rd
IEEE Symposium on Foundations of Computer Science, pages 14--H23, 1992.
5. Arora and 5. Safra. Probabilistic checking of proofs: A new characterization
of NP. In Proceedings of the 33rd Annual IEEE Symposium of the Foundations
of Computer Science, pages 2--H13,1992.
L. Babai. Transparent (holographic) proofs. Springer- Verlag Lecture Notes on
Computer Science, 10th Annual Synposium on Theoretical Aspects of Computer
Science, 665:525--H533,1993.
D. Beaver and J. Feigenbaum. Hiding instances in multioracle queries. In
Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer
Science, Springer Verlag LNCS 415, pages 37--H48,1990.
L. Babai and L. Fortnow. Arithmetization: A new method in structural com-
plexity theory. Computational Complexity, 1:41--H66,1991.
21
[BF91]
[BPL9l] L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has
two-prover interactive protocols. Computational Complexity, 1:3--H40,1991.
[BFLS9l] L. Babai, L. Fortnow, L. Levin, and M. Szegedy. Checking computations in
polylogarithmic time. In Proceedings of the 23rd Annual ACM Symposium on
Theory of Computing, pages 21--H31,1991.
[BGLR93]
[BK89]
[BLR90j
[B1u88]
[dW70]
[FGLSS91]
M. Bellare, 5. Goidwasser, C. Lund, and A. Russell. Efficient probabilistically
checkable proofs. In Proceedings of the 25th Annual ACM Symposium on Theory
of Computing, pages 294--H304,1993.
M. Blum and 5. Kannan. Program correctness checking ... and the design
of programs that check their work. In Proceedings of the 21st Annual ACM
Symposium on Theory of Computing, pages 86--H97,1989.
M. Blum, M. Luby, and R. Rubinfeld. Self?testing/correcting with applications
to numerical problems. In Proceedings of the 22nd Annual ACM Symposium on
Theory of Computing, pages 73--H83, 1990.
M. Blum. Designing programs to check their work. Technical Report TR--H88--H
009, International Computer Science Institute, 1988.
Van der Waerden. Algebra, volume 1. Prederick Ungar Publishing Co., Inc.,
1970.
U. Feige, 5. Goldwasser, L. Lovasz, 5. Safra, and M. Szegedy. Approximating
clique is alinost NP-complete. In Proceedings of the 32nd IEEE Symposium on
Foundations of Computer Science, pages 2--H12,1991.
[Fri93] K. Friedl. d + 2 suffices. Manuscript, 1993.
[GLRSW9lj P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson. Self-
testing/correcting for polynomials and for approximate functions. In Proceedings
of the 23rd Annual ACM Symposium on Theory of Computing, pages 32--H42,
1991.
[Kan90]
[Lip9 lj
[Lun92j
5. Kannan. Program Result Checking with Applications. PhD thesis, University
of California, Berkeley, 1990.
R. Lipton. New directions in testing. Distributed Computing and Cryptography,
DIMACS Series in Discrete Math and Theoretical Computer Science, American
Mathematical Society, 2:191--H202,1991.
C. Lund. The Power of Interaction. ACM Distinguished Dissertations. The
MIT Press, 1992.
M. Naor, April 1992. Personal Communication.
[Nao92]
22
[RS92]
[Rub9O]
[She91]
[Sud92j
R. Rubinfeld and M. Sudan. Testing polynomial functions efficiently and over
rational domains. In Proceedings of the 3rd Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 23--H43,1992.
R. Rubinfeld. A Mathematical Theory of Self-Checking, Self-Testing and Self-
Correcting Programs. PhD thesis, University of California at Berkeley, 1990.
A. Shen. Personal Communication, May 1991.
M. Sudan. Efficient Checking of Polynomials and Proofs and the Hardness of
Approximation Problems. PhD thesis, University of California at Berkeley, 1992.
A Appendix
A.1 Evenly spaced points
The following algorithm may be used to test if a function f(O) on m evenly spaced points --H
x,x t h,. . . ,x + (m 1)h --H (where m> d+ 1) agrees with a degree d polynomial.
for i = 1 to dtl do
for j = 1 to m z
f(t)(x +jh) --H f(?--H')(x + (j + 1)h) --H f(?--H')(x +jh)
endfor
endfor
verify f(d+l)(xtjh)=o, for all j??0,...,m--Hd--H2i.
The correctness of this algorithm follows from the following well-known fact:
Fact 26 f(?)(x) is a degree d--Hi polynomial if and only if f(i?1) is a degree d--Hi+1 polynomial.
(Follows from the fact that f(?) acts as the discrete derivative of f(i?l).)
This implies that f(d) is a constant if and only if f(O) is a degree d polynomial, implying
in turn that f(d+1) is identically zero if and only if f(O) is a degree d polynomial. Observe
further that the algorithm performs O(md) additions and subtractions and no multplications.
Lastly it can also be checked that in case m d + 2, then algorithm simply verifles that
Ztd+1 ??f(0)(x + ih) = 0, where ot? =
23
A.2 Characterizations
Lemma 27 (axis parallel lines) f : z?m Zp is a polynomial in m variables of de-
gree at most d in each variable if and only if for all i ? f1,. . . ,mi, Pi ? Zp (j # i),
f(Pi.. .Pi--Hi, ..... `Pm) is a polynomial in X? of degree at most d.
Proof [Sketch]: It is clear that every polynomial of degree d in each variable restricted
to axis parallel lines, behaves as a univariate polynomial of degree d. The other direction
can be proved by induction on m. The base case m 1 is obvious, For general m> 1, let
f1(x1,... , Xm--Hi) be the function f(x1,... , Xm?l, i). By induction f? is a polynomial of degree
din m--H1 variables. Now consider the function h(x1,... , Xm) Zdi?o6?d)(xm)ft(xi.... , Xm--Hi)
(where ?d) is the unique polynomial of degree d in one variable which is 1 at Xm = i and 0
for other values of Xm E ?0,..., di).
It is clear by construction that h is a polynomial of degree at most d in each variable. We
now argue that f and h are identical. Fix x1 = P1...., Xm?l = Pm-i' It is clear that
h(x1,. ., ,xm) = f(x1,. .. ,Xm) for Xm ? ?o,.. . ,di. Moreover, both h and f are degree d
polynomials in Xm which agree at d + 1 places. Hence f and h must agree at all values of
Xm. Since this held for any choice of Pi's, f and h agree everywhere. ?
Lemma 28 (general lines) For p > 2d + 1, f : z?m " Zp is a polynomial in m variables
of total degree at most d if and only if Vx, h ? Zr, f(x + t k) is a univariate polynomial in
t of degree at most d.
Proof: It is clear that every polynomial restricted to lines must become a degree d
polynomial in the parameter describing the line. Here we prove the other direction of the
characterization. We first observe that since the set of all lines includes the axis parallel
lines, we can use Lemma 27 to show that f is a polynomial in m variables with degree at
most d in each variable. Having got this weak characterization, we will now strengthen this
to a tighter one. By induction on the number of variables, we can assume that f restricted
to any value of the last variable Xm is a polynomial of total degree at most d in the variables
Xm?l. Thus f becomes a function in x1 through Xm of total degree d' ? 2d.
Assume for contradiction that d' > d. Now consider the function f(t. ? for h ER Zp?
The coefficient of td' is a polynomial in h of degree d' which with probability at least 1 --H
p
should be non-zero. (Note that to make this probability positive, we need 2d ? p.) Thus f
restricted to this line is a polynomial of degree d' > d, which violates the given condition on
24
