Self-Testing without the Generator Bottleneck.
Suppose P is a program designed to compute a function f defined on a group G. The task of self-testing P, that is, testing if P computes f correctly on most inputs, usually involves testing explicitly if P computes f correctly on every generator of G. In the case of multivariate functions, the number of generators, and hence the number of such tests, becomes prohibitively large.  We refer to this problem as the  generator bottleneck. We develop a technique that can be used to overcome the generator bottleneck for functions that have a certain nice structure, specifically if the relationship between the values of the function on the set of generators is easily checkable. Using our technique, we build the first efficient self-testers for many linear, multilinear, and some nonlinear functions. This includes the FFT, and various polynomial functions. All of the self-testers we present make only O(1) calls to the program that is being tested. As a consequence of our techniques, we also obtain efficient program result-checkers for all these problems.
Introduction
. The notions of program result-checking, self-testing, and self-correcting
as introduced in [4, 17, 5] are powerful tools for attacking the problem
of program correctness. These methods offer both realistic and efficient tools for
software verification. Various useful mathematical functions have been shown to have
self-testers and self-correctors; some examples can be found in [5, 3, 17, 9, 14, 18, 1,
19, 21, 6]. The theoretical developments in this area are at the heart of the recent
breakthrough results on probabilistically checkable proofs and the subsequent results
that show non-approximability of hard combinatorial problems.
Suppose we are given a program P designed to compute a function f . Informally,
a self-tester for f distinguishes the case where P computes f correctly always from
the case where P errs frequently. A result-checker for a function f takes as input
a program P and an input q to P , and outputs PASS when P correctly computes
f always and outputs FAIL if P (q) 6= f(q). Given a program P that computes f
correctly on most inputs, a self-corrector for f is a program P sc that uses P as an
oracle and computes f correctly on every input with high probability.
1.1. Definitions and Basics. Before we discuss our results, we present the
basic definitions of testers, checkers, etc., and state some desirable properties of these
programs. Let f be a function on a domain D and let P be a program that purports to
compute f . The testers, correctors, and checkers we define are probabilistic programs
that take P as an oracle, and in addition, take one or more of the following parameters
as input: an accuracy parameter ffl that specifies the conditions that P is expected to
This paper unifies the preliminary versions which appeared in the 27th Annual Symposium
on Theory of Computing [10] and in the 15th Annual Foundations of Software Technology and
Theoretical Computer Science [16].
y Department of Computer Science, Cornell University, Ithaca, NY 14853-7501
(ergun@cs.cornell.edu). This work is partially supported by ONR Young Investigator Award
N00014-93-1-0590, the Alfred P. Sloan Research Award, and NSF grant DMI-91157199.
z Department of Computer Science, Cornell University, Ithaca, NY 14853-7501
(ravi@cs.cornell.edu). This work is partially supported by ONR Young Investigator Award
N00014-93-1-0590, the Alfred P. Sloan Research Award, and NSF grant DMI-91157199.
x Department of Computer Science, University of Houston, Houston,
Most of this work performed while the author was at SUNY/Buffalo, supported in part by K. Regan's
NSF grant CCR-9409104.
UN, S. R. KUMAR, AND D. SIVAKUMAR
meet, and a confidence parameter ae that is an upper bound on the probability that
the tester/corrector/checker fails to do its job. The following definitions formalize the
notions of self-tester [5], self-corrector [5, 17], and result-checker [4].
Definition 1.1 (Self-Tester). An ffl-self-tester for f is a probabilistic oracle
program T that, given ae ? 0, satisfies the following conditions:
ffl Pr x2D [P
Definition 1.2 (Self-Corrector). An ffl-self-corrector for f is a probabilistic oracle
program P sc that, given any input y, and ae ? 0, satisfies the following condition:
ffl Pr x2D [P
Definition 1.3 (Result-Checker). A checker (or result-checker) for f is a probabilistic
oracle program C that, given an input y and ae ? 0, satisfies the following
conditions:
ffl Pr x2D [P outputs PASS, and
We now list three important properties that are required of self-testers, self-
correctors, and result-checkers. For definiteness, we state these for the case of self-
testers. First, the self-tester T should be computationally different from and more
efficient than any program that computes f [4]. This restriction ensures that T does
not implement the obvious algorithm to compute f (and hence could harbor the same
set of bugs, or be computationally inefficient). Furthermore, this ensures that the
running time of T is asymptotically better than the running time of the best known
algorithm for f . The second important property required of T is that it should not
require the knowledge of too many correct values of f . In particular, this rules out
the possibility that T merely keeps a large table of the correct values of f for all
inputs. The third important property required of a self-tester is efficiency : an efficient
self-tester should only make O(1=ffl; lg(1=ae)) calls to P . For constant ffl and ae, an
efficient self-tester makes only O(1) calls to the program. (In the rest of the paper,
we often write O(1) as a shorthand for O(1=ffl; lg(1=ae)), particularly when discussing
the dependence on other parameters of interest.)
The following well-known lemma summarizes some relationships between the notions
of self-testers, self-correctors, and result-checkers. For the reader's convenience,
we sketch the idea of the proof of this lemma, suppressing the details of the accuracy
and confidence parameters.
Lemma 1.4 ([5]). (a) If f has a self-tester and a self-corrector that make O(1)
calls to the program, then f has a result-checker that makes O(1) calls to the program.
(b) If f has a result-checker, then it has a self-tester.
Proof. (Sketch) For part (a), suppose that f has a self-tester and a self-corrector.
Given an input y and oracle access to a program P , first self-test P to ensure that
it doesn't err too often. If the self-tester finds P to be too erroneous, output FAIL.
Otherwise, compute f(y) by using the self-corrector for P sc and the program P , and
output PASS iff P
Clearly a perfect program always passes. Suppose P (y) 6= f(y). Then one of
the following two cases must occur. The program is too erroneous, in which case the
self-tester, and hence the checker, outputs FAIL. The program is not too erroneous,
in which case the self-corrector computes f(y) correctly with high probability, so the
checker detects that P (y) 6= P sc (y) and outputs FAIL.
For part (b), suppose that f has a result-checker. By using the result-checker to
test if P randomly chosen inputs x, the fraction of inputs x for
which P (x) 6= f(x) can be estimated. Output PASS iff this fraction is less than ffl.
A useful tool in constructing self-correctors is the notion of random self-reducibility .
The fine details of this notion are beyond the scope of this paper, and we refer the
reader to the papers [3, 17] (see also the survey paper [11]). Informally, a function
f is randomly self-reducible if evaluation of f on an input can be reduced efficiently
to the evaluation of f on one or more random inputs. For a quick example, note
that linear functions are randomly self-reducible: to compute f(x), it suffices to pick
a random r compute f(x + r) and f(r), and finally obtain
All functions that we consider in this paper are efficiently randomly self-reducible;
therefore, whenever required, we will always assume that efficient self-correction is
possible.
1.2. Building Self-Testers using Properties. The process of self-testing
whether a program P computes a function f correctly on most inputs is usually
a two-step strategy. First perform some tests to verify that P agrees on most inputs
with a function g that belongs to a certain class F of functions that contains f . Then
perform some additional tests to verify that the function g is, in fact, the intended
function f .
The standard way to test whether P agrees with some function in a class F of
functions is based on the notion of a robust property . Informally, property I is said to
be a robust characterization of a function family F if the following two conditions hold:
(1) every f 2 F satisfies I, and (2) if P is a function (program) that satisfies I for
most inputs, then P must agree with some g 2 F on most inputs. For example, Blum,
Luby, and Rubinfeld [5] establish that the property of linearity
serves as a robust property for the class of all linear functions, and use this to build
self-testers for linear functions. This generic technique was first formalized in [19].
(Robust Property). A property is a predicate I f
property I f (~x) is (ffl; ffi)-robust for a class of functions F over a domain
D, if it satisfies the following conditions:
\Theta

ffl If a function (program) P satisfies Pr ~x2D k [I P
there is a function g such that
that is, (9g 2 F) such that P agrees with g on all but ffi fraction of inputs.
We now outline the process of building self-testers using robust properties (cf. [5]).
Let D be a (finite) group with generators e some class of
functions from D into some range R. Further assume that the functions in F possess
the property of random self-reducibility, and can hence be self-corrected efficiently.
Suppose P is a program that purports to compute a specific function f 2 F . Let
I f (~x) be a robust property that characterizes F .
As mentioned earlier, the process of building self-testers is a two-step process.
In the first step, we will ensure that that the program P agrees with some function
2 F on most inputs. To do this, we will use the fact that I f is a robust property
that characterizes F . Specifically, the self-tester will estimate the fraction of k-tuples
holds. If this fraction is at least 1 \Gamma ffl, then by the robustness
of I f , it follows that there is some g 2 F that agrees with P on all but ffi fraction of
D. The required estimation can be carried out by random sampling of ~x and testing
the property I f .
UN, S. R. KUMAR, AND D. SIVAKUMAR
The next step is to verify that the function g is the same as the function f that
P purports to compute. This is achieved by testing that g(e i
generator of the group D. If this is true, then by an easy induction it would follow
that g j f . An important point to be mentioned here is that the self-tester has access
only to P and not to g; the function g is only guaranteed to exist. Nevertheless,
the required values of g may be obtained by using a self-corrected version P sc of P .
Another point worth mentioning is that to carry out this step, the self-tester needs
to know the values of f on every generator of D.
1.3. The Generator Bottleneck. An immediate application of the basic
method outlined above to functions whose domains are vector spaces of large dimension
suffers from a major efficiency drawback. For example, if the inputs to the
function f are n-dimensional vectors (or n \Theta n matrices), then the number of generators
of the domain is n (resp. n 2 ). The straightforward approach of exhaustively
testing if P sc agrees with f on each generator by making n (resp.
furthermore, the self-tester built this approach requires the knowledge of the correct
value of f on n (resp. is large, this makes the overhead in the
self-testing process too high. This issue is called the generator bottleneck problem.
In this paper, we address the generator bottleneck problem, and solve it for a
fairly large class of functions that satisfy some nice structural properties. The self-
testers that we build are not only useful in themselves, but are also useful in building
efficient result-checkers, which are important for practical applications.
1.4. Our Results. We present a fairly general method of overcoming the generator
bottleneck and testing multivariate functions by making only O(1) calls to the
program being tested.
First we investigate the problem of multivariate linear functions (i.e., the functions
f satisfying We show a general technique that can be applied
in a natural vector space setting. The main idea is to obtain an easy and uniform
way of "generating" all generators from a single generator. Using this idea, we give a
simple and powerful condition for a linear function f to be efficiently self-testable on
a large vector space. We then apply this scheme to obtain very efficient self-testers
for many functions. This includes polynomial differentiation (of arbitrary order),
polynomial integration, polynomial "mod" function, etc. We also obtain the first
efficient self-tester for Fourier transforms.
We then extend this method to the case of multilinear functions (i.e., functions
f that are linear in each variable when the other variables are fixed). We build an
efficient tester for polynomial multiplication as a consequence. Another application
we give is for large finite fields: we show that multilinear functions over finite field
extensions of dimension n can be efficiently self-tested with O(1) calls, independent of
the dimension n. We also provide a new efficient self-tester for matrix multiplication.
We next extend the result to some nonlinear functions. We give self-testers for
exponentiation functions that avoid the generator bottleneck. For example, consider
the function that computes the square of a polynomial over a finite field:
Here we do not have the linearity property that is crucial in the proof for the linear
functions. Instead, we use the fact that the Lagrange interpolation identity (cf. Fact
4.1) for polynomials gives a robust characterization. We exhibit a self-tester for the
function that makes O(d) calls to the program being tested. Extending the
technique when f is a constant degree exponentiation to the case when f is a constant
degree polynomial (eg., is a polynomial over a finite field)
is much harder. First we show a reduction from multiplication to the computation of
low-degree polynomials. Using this reduction and the notion of a result-checker, we
construct a self-tester for degree d polynomials over finite field extensions of dimension
n that make O(2 d ) calls to the program being tested.
1.5. Related Work. One method that has been used to get around the generator
bottleneck has been to exploit the property of downward self-reducibility [5].
The self-testers that use this property, however, have to
make\Omega\Gamma383 n) calls to the
program depending on the way the problem decomposes into smaller problems. For
instance, a tester for the permanent function of n \Theta n matrices makes O(n) calls to
the program, whereas a tester for polynomial multiplication that uses similar principles
makes O(log n) calls. In [5] a bootstrap tester for polynomial multiplication that
makes O(log n) calls to the program being tested is given. It is already known that
matrix multiplication can be tested (without any calls to the program) using a result-
checker due to Freivalds [13]. The idea of Freivalds' matrix multiplication checker can
also be adapted to build testers for polynomial multiplication that make no calls to
the program being tested. This approach, however, requires the underlying field to be
large (have at least (2 is the degree of the polynomials being
multiplied, and fl is a positive constant). Moreover, this scheme requires the tester
to perform polynomial evaluations, whereas ours does not. For Fourier transforms, a
different result-checker that uses preprocessing has been given independently in [6].
A Useful Fact. The following fact, a variant of the well-known Chernoff-Hoeffding
bounds, is often very useful in obtaining error-bounds in sampling 0/1 random variables
[15]:
Fact 1.6. Let Y independently and identically distributed 0=1 random
variables with means -. Let ' - 2. If N - (1=-)(4
e
Organization of the Paper. Section 2 discusses the scheme for linear functions
over vector spaces; x3 extends the scheme for multilinear functions; x4 outlines the
approach for non-linear functions.
2. Linear Functions over Vector Spaces. In this section, we address the
problem of self-testing linear functions on a vector space without the generator bot-
tleneck. We demonstrate a general technique to self-test without the generator bottleneck
and provide several interesting applications of our technique.
Definitions. Let V be a vector space of finite dimension n over a field K , and let f
be a function from V into a ring R. We are interested in building a self-tester for the
case where f(\Delta) is a linear function, that is, f(cff
and c 2 K . For the unit vector that has a 1 in the i-th
position and 0's in the other positions. The vectors e 1 a collection of
basis vectors that span V . Viewed as an Abelian group under vector addition, V is
generated by e We assume that the field K is finite, since it is not clear how
to choose a random element from an infinite field.
The property of linearity I f (ff; fi) was shown to
be robust in [5]. Using this and the generic construction of self-testers from robust
properties, one obtains the following self-tester for the function f :
6 F. ERG -
UN, S. R. KUMAR, AND D. SIVAKUMAR
Property Test:
Repeat O( 1
ae ) times
Pick ff; fi 2R V
Verify
Reject if the test fails
Generator Tests:
For
Verify P sc
If P passes the Property Test then we are guaranteed the existence of a linear
function g that is close to P . There are, however, two problems with the Generator
Tests: one is that the self-tester is inefficient-if the inputs are vectors of size n, the
self-tester makes O(n) calls to the program, which is not desirable. Secondly, the
self-tester needs to know the correct value of f on n different points, which is also
undesirable. Our primary interest is to avoid this generator bottleneck and solve both
of the problems mentioned. The key idea is to find an easy and uniform way that
"converts" one generator into the next generator. We illustrate this idea through the
following example.
Example. Let Pn denote the additive group of all degree n polynomials over a
field K . The elements multiplying any generator x k
by x gives the next generator x k+1 . For a polynomial q 2 Pn and a scalar c 2 K , let
denote the function that evaluates q(c). Clearly E c is linear and satisfies the
simple relation E c Suppose P is a program that purports to compute
and assume that P has passed Property Test given above. Then we know by
robustness of linearity that there is a linear function g that agrees with P on most
inputs. Note that g can be computed correctly with high probability via the self-
corrector (which are easy to construct for linear functions [5]). Now, rather than
verify that g(x k of Pn , we may instead verify that g
satisfies the property By an easy induction, this implies
that g agrees with E c at all the generators. By linearity of g, it follows that g agrees
with E c on all inputs.
We are now faced with the task of verifying
is too expensive to be tried explicitly and exhaustively. Instead, we prove that it
suffices to check with O(1) tests that almost everywhere that we look
at. That is, pick many random q 2 Pn , ask the program P sc to compute the values
of g(q) and g(xq) and cross-check that holds. In other words, we prove
that the property J g (q) j robust (in a restricted sense), under the
assumption that g is linear. (In its most general interpretation, robustness guarantees
the existence of h that satisfies and that agrees with
g on a large fraction of inputs. We actually show that h j g, hence the "restricted
sense.") Notice that the number of points on which the self-tester needs to know the
value of f is just one, in contrast to n as in the original approach of [5].
Generalization via the Basis Rotation Function '. We note that this idea has a
natural generalization to vector spaces. Let ' denote the basis rotation function, i.e.,
the linear operator on a vector space V that "rotates" the coordinate axes that span
. ', which can be viewed as a matrix, defines a one-to-one correspondence from the
set of basis vectors to itself: for every i, '(e i . The computational payoff
is achieved when there is a simple relation between f(ff) and f('(ff)) for all vectors
specifically, we show that the generator bottleneck can be avoided if
there is an easily computable function h ';f such that
for all ff 2 V . (For instance, for polynomial evaluation E c ,
From here on, when obvious, we drop the suffix f and simply denote h ';f as h ' . If the
function f is linear, the linearity of ' implies that h ' is linear in its second argument
in the following sense: h ' (ff What is
more important is that h ' be easy to compute, given just ff and f(ff). Using this
scheme, we show that many natural functions f have a suitable candidate for h ' .
The Generator Tests of [5] can now be replaced by:
Basis Test:
Verify P sc
Inductive Test:
Repeat O( 1
ae ) times
Pick ff 2R V
Verify P sc
Reject if the test fails
The following theorem proves that this replacement is valid:
Theorem 2.1. Suppose f is a linear function from the vector space V into a
ring R, and suppose P is a program for f .
(a) Let ffl ! 1=2, and suppose P satisfies the following condition:
Then the function g defined by is a linear
function on V , and g agrees with P on at least 1 \Gamma 2ffl fraction of the inputs.
(b) Furthermore, suppose h ' (ff; satisfies the following
conditions:
(3) Pr ff2V [g('(ff)) 6= h ' (ff; g(ff))] - ffl, where ff is such that '(ff) is defined.
Remarks. The above theorem merely lists a set of properties. The fact that this
set yields a self-tester is presented in Theorem 2.2. Note that hypotheses (1), (2), and
(3) above are conditions on P and g, not tests performed by a self-tester.
Proof. The proof that the function g is linear and P sc computes g (with high
probability) is due to [5]. For the rest of this proof, we will assume that g is linear
and that it satisfies conditions (2) and (3) above.
We first argue that it suffices to prove that if the conditions hold, then for every
agrees with f on the first basis
vector. For i ? 1, the basis vector e i can be obtained by '(e
would follow that g computes f correctly on all
the basis vectors. Finally, since g is linear, it computes f correctly on all of V , since
the vectors in V are just linear combinations of the basis vectors.
Now we show that condition (3) implies that 8ff 2 V ,
an arbitrary element ff 2 V . We will show that the probability over a random
UN, S. R. KUMAR, AND D. SIVAKUMAR
that positive. Since the equality is independent of fi and
holds with nonzero probability, it must be true with probability 1. Now
Pr
\Theta
The first equality in the above is just rewriting. The second equality follows from
the linearity of '. The third equality follows from the fact that g is linear. If the
random variable fi is distributed uniformly in V , the random variables fi and ff \Gamma fi
are distributed identically and uniformly in V . Therefore, by the assumption that g
satisfies condition (3), the fourth equality fails with probability at most 2ffl. The fifth
equality uses the fact that h ' is linear, and the last equality uses the fact that g is
linear.
The foregoing theorem shows that if P (and g) satisfy certain conditions, then g,
which can be computed using P , is identically equal to the function f . The self-tester
comprises the following tests: Linearity Test, Basis Test, and Inductive Test.
Theorem 2.2. For any ae ! 1 and ffl ! 1=2, the above three tests comprise a
2ffl-self-tester for f . That is, if a program P computes f correctly on all inputs, then
the self-tester outputs PASS with probability 1, and if P computes f incorrectly on
more than 2ffl fraction of the inputs, then the self-tester outputs FAIL with probability
at least 1 \Gamma ae.
Proof. In performing the three tests, the self-tester is essentially estimating the
probabilities listed in conditions (1), (2), and (3) of the hypothesis of Theorem 2.1.
Note that condition (2) does not involve any probability; rather, the self-tester uses
P sc to compute g(e 1 ). By choosing O((1=ffl) log(1=ae)) samples in Linearity Test
and Inductive Test and by using the self-corrector with confidence parameter ae=3
in Basis Test the self-tester ensures that its confidence in checking each condition
is at least 1 \Gamma (ae=3).
correctly, the tester always outputs PASS. Con-
versely, suppose the tester outputs PASS. Then with probability ae, the hypotheses
of Theorem 2.1 are true. By the conclusion of Theorem 2.1, it follows that a function
g that is identical to f exists and that g equals P on at least 1 \Gamma 2ffl fraction of the
inputs.
2.1. Applications. We present some applications of Theorem 2.2. We remind
the reader that a linear function f on a vector space V is efficiently self-testable without
the generator bottleneck if there is a (linear) function h ' that is easily computable
and that satisfies In each of our applications
f , we show that a suitable function exists that satisfies the above condi-
tions. Recall the example of the polynomial evaluation function E c
the identity E c holds; in the applications below, we will only establish
similar relationships. Also, for the sake of simplicity, we do not give all the technical
parameters required; these can be computed by routine calculations following the
proofs of the theorems in the last section.
Our applications concern linear functions of polynomials. We obtain self-testers
for polynomial evaluation, Fourier transforms, polynomial differentiation, polynomial
integration, and the mod function of polynomials. Moreover, the vector space setting
lets us state some of these results in terms of the matrices that compute linear
transforms of vector spaces.
Let Pn ' K [x] denote the group of polynomials in x of degree - n over a field
K . The group Pn forms a vector space under usual polynomial addition and scalar
multiplication by elements from K . The polynomials
polynomial
has the vector representation (q
basis rotation function ' in this case is just multiplication by x, thus
that multiplying q by x results in a polynomial of degree n+ 1. To handle this minor
detail, we will assume that the program works over the domain Pn+1 and we conclude
correctness over Pn .
Polynomial Evaluation. For any c 2 K , let E c (q) denote, as described before,
the function that returns the value q(c). This function is linear. Moreover, the
relation between E c (xq) and E c (q) is simple and linear: E c To self-test
a program P that claims to compute E c , the Inductive Test is simply to choose
many random q's, and verify that P sc holds.
Operators and the Discrete Fourier Transform. If
are distinct elements of K , then one may wish to evaluate a polynomial q 2 Pn
simultaneously on all points. The ideas for E c extend easily to this case, for
any u 2 K , and these relations hold simultaneously.
Let ! be a principal (n 1)-st root of unity in K . The operation of converting a
polynomial from its coefficient representation to pointwise evaluation at the powers of
! is known as the Discrete Fourier Transform (DFT). DFT has many fundamental applications
that include fast multiplication of integers and polynomials. With our nota-
tion, the DFT of a polynomial q 2 Pn is simply F
The DFT F is linear, and F that here the
function h is really n coordinate functions h n. The self-tester will
simply choose q's randomly, request the program to compute F (q) and F (xq), and
verify for each holds.
This suggests the following generalization (for the case of arbitrary vector spaces).
Simultaneous evaluation of a polynomial at d corresponds to
multiplying the vector p by a
. The ideas
used to test simultaneous evaluation of polynomials and the DFT extend to give a
self-tester for any linear transform that is represented by a Vandermonde matrix.
The matrix for the DFT can be written as a Vandermonde matrix F , where
. The inverse of the DFT, that is, converting a polynomial from pointwise
representation to coefficient form, also has a Vandermonde matrix whose entries are
given by e
\Gammaij . It follows that the inverse Fourier Transform can be
self-tested efficiently. Another point worth mentioning here is that in carrying out
the Inductive Test the self-tester does not have to compute det F . All it needs to
do is verify that for many randomly chosen q's, the identity ( e
F (q))[i]
holds.
Operators in Elementary Jordan Canonical Form. A linear operator M is said to
be in elementary Jordan canonical form if all the diagonal entries of M are c for some
all the elements to the left of the main diagonal (the first non-principal
diagonal in the lower triangle of M) are 1's. It is easy to verify that
where M 0 is a matrix that has a \Gamma1 in the top left corner and a 1 in the bottom right
UN, S. R. KUMAR, AND D. SIVAKUMAR
corner and zeroes elsewhere. Therefore, for every in the
vector space, This gives an easy way to
implement the Inductive Test in the self-tester.
An attempt to extend this to matrices in Jordan canonical form, or even to
diagonal matrices, seems not to work. If, however, a diagonal or shifted diagonal
matrix has a special structure, then we can obtain self-testers that avoid the generator
problem. For example, the matrix corresponding to the differentiation of polynomials
has a special structure: it contains the entries n; on the diagonal above
the main diagonal.
Differentiation and Integration of Polynomials. Differentiation of polynomials is
a linear function We have the explicit form for
Integration of polynomials is a linear function I : Pn ! Pn+1 . The explicit form for h
is Even though this does not readily fit into our framework
(since it is not of the form the proof of Theorem 2.1 can be
easily modified to handle this case using the linearity of I . For completeness, we spell
out the details for the robustness of the Inductive Test which is the only change
required.
Lemma 2.3. If g : Pn ! Pn+1 is a linear function that satisfies Pr q2Pn [g(xq) 6=
Proof.
Pr
r2Pn
\Theta
Since the event holds with positive probability and is
independent of r, it holds with probability one.
Thus we can avoid the generator bottleneck for these functions. This can be
considered as a special case of the previous application.
Higher Order Differentiation of Polynomials. Let D k denote the k-th differential
operator. It is easy to write a recurrence-like identity for D k in terms of D
This gives us a self-tester only in the library setting described in [5, 20], where one
assumes that there are programs to compute all these differential operators. If we
wish to self-test a program that only computes D k and have no library of lower-order
differentials, this assumption is not valid. To remedy this, we will use the following
lemma, which is proved in the Appendix.
Lemma 2.4. If q is a polynomial in x of degree - k, then
Using this identity, the self-tester can perform an Inductive Test. The robustness
of the Inductive Test can be established as in the proof of Theorem 2.1. For
completeness, we outline the key step here. Let c i denote the coefficient of the term
in the sum in Lemma 2.4. Thus c
(\Gammax) k\Gammai .
Lemma 2.5. If g is a linear function that satisfies Pr q2Pn [
Proof.
Pr
r2Pn
\Theta X
Here the first equality is rewriting, the second equality holds with probability 1\Gamma2ffl
by the assumption that Pr q [
the event
holds with positive probability and is independent of r, it holds with probability one.
Thus, testing if g satisfies this identity for most q suffices to ensure that g satisfies
this identity everywhere. If g does satisfy this identity, then we know the following:
To conclude that g j D k by induction, we need to modify Basis
Test to test k base cases: if
Mod Function. Let ff 2 K [x] be a monic irreducible polynomial. Let M ff (q)
denote the mod function with respect to ff, that is, M ff ff. This is a linear
function when the addition is interpreted as mod ff addition. Since ff is monic, the
degree of M ff (q) is always less than deg ff. If c 2 K is the coefficient of the highest
degree term in M ff (q), we have
ae xM ff (q) if deg xM ff (q) ! deg ff
As before, in testing if a program P computes the function M ff , step (3) of the
self-tester is to choose many q's at random, compute P sc (q) and P sc (xq), and verify
that one of the identities P sc holds (depending
on the degree of q).
3. Multilinear Functions. In this section we extend the ideas in x2 to multilinear
functions. A k-variate function f is called k-linear if it is linear in each of its variables
when the other variables are fixed, i.e., f(ff
Our main motivating example for a multilinear function is polynomial multiplication
which is bilinear. Note that the domain of f is
generated by n 2 generators of the form (i.e., pairs of generators
of suppose we wish to test P that purports to compute f . The naive
approach would require doing the Generator Tests at these n 2 generators. This
requires O(n 2 ) calls to P , rendering the self-tester highly inefficient. Blum, Luby,
and Rubinfeld [5] give a more efficient bootstrap self-tester that makes O(log O(k) n)
calls to P . It can be seen that for general k-linear functions, their method can be
extended to yield a tester that makes O(log O(k) n) calls to P . (In our context, it is
allowable to think of k as a constant since changing k results in an entirely different
function f .) We are interested in reducing the number of calls to P with respect to
UN, S. R. KUMAR, AND D. SIVAKUMAR
the problem size n for a specific function f . The complexity of the tester we present
here is independent of n, and the self-tester is required to know the correct value of
f at only one point. As in the previous section, our result applies to many general
multilinear functions over large vector spaces.
As before, we define a set of properties depending on f , that, if satisfied by P ,
would necessarily imply that P must be the same as the particular multilinear function
f . For simplicity, we present the following theorem for f that is bilinear. This is an
analog of Theorem 2.1 for multilinear functions.
Theorem 3.1. Suppose f is a bilinear function from V 2 into a ring R, and
suppose P is a program for f .
(a) Let ffl ! 1=4, and suppose P satisfies the following condition:
Then the function g defined by g(ff
is a bilinear function on V 2 , and g agrees
with P on at least 1 \Gamma 2ffl fraction of the inputs.
(b) Furthermore, suppose g satisfies the following conditions:
Proof. A simple extension of the proof in [5] shows that g is bilinear. (Better
bounds on ffl via a different test can be obtained by appealing to [2].) As in the
proof of Theorem 2.1, it suffices to show that given the three conditions, a stronger
version of condition (3) holds: g('(ff 1
h (2)
. With the addition of this last property, it can
be shown that g j f . Taking condition (2) that g(e 1 as the base case
and inducting by obtaining (e via an application of '
to either generator for all 1 be shown that g(e i
bases elements This, combined with the bilinearity property of g, implies
the correctness of g on every input.
Now we proceed to show the required intermediate result that given conditions
(1) and (2), g satisfies the stronger version of condition (3) that we require above:
Pr
\Theta
h (2)
The first equality is a rewriting of terms. Multilinearity of g implies the second
and third equalities. If the probability Pr[g(ff
the fourth equality fails with probability less than 4ffl. The rest of the equality follows
from the multilinearity of h (2)
' and g. If ffl ! 1=4, this probability is nonzero. Since the
first and last terms are independent of are equal with nonzero probability,
the result follows. A similar approach works for h (1)
' as well.
Multilinearity Test:
Repeat O( 1
ae ) times
Pick
Verify
Reject if the test fails
Basis Test:
Verify P sc
Inductive Test:
Repeat O( 1
ae ) times
Pick
Verify
Verify
Reject if the test fails
Note that in the latter two tests we use a self-corrected version P sc of P . The notion
of self-correctors for multilinear functions over vector spaces is implied by random
self-reducibility.
It is easy to see that Theorem 3.1 extends to an arbitrary k-linear function so
long as ffl ! 1=2 k . Thus, we obtain the following theorem whose proof mirrors that of
Theorem 2.2.
Theorem 3.2. If f is a k-variate linear function, then for any ae ! 1 and
, the above three tests comprise a 2 k ffl-self-tester for f that succeeds with
probability at least 1 \Gamma ae.
3.1. Applications. Let q 1 ; q 2 denote polynomials in x. The function M(q
that multiplies two polynomials is symmetric and linear in each variable. Moreover,
since polynomial multiplication has an efficient
self-tester.
An interesting application of polynomial multiplication, together with the mod
function described in x2.1, is the following. It is well-known that a degree n (finite)
extension K of a finite field F is isomorphic to the field F[x]=(ff), where ff is an
irreducible polynomial of degree n over F. Under this isomorphism, each element of
K is viewed as a polynomial of degree - n over F, addition of two elements
is just their sum as polynomials, and multiplication of q
by q 1 q 2 mod ff. It follows that field arithmetic (addition and multiplication) in finite
extensions of a finite field can be self-tested without the generator bottleneck, that is,
the number of calls made to the program being tested is independent of the degree of
the field extension.
3.2. Matrix Multiplication. Let Mn denote the algebra of n \Theta n matrices over
Mn !Mn denote matrix multiplication. Matrix multiplication
14 F. ERG -
UN, S. R. KUMAR, AND D. SIVAKUMAR
is a bilinear function; however, since it is a matrix operation rather than a vector oper-
ation, it requires a slightly different treatment from the general multilinear functions.
Mn , viewed as an additive group, has n 2 generators; one possible set of generators is
where each generator E i;j is a matrix that has a 1 in position
We note that any generator E i;j can be converted into any
other generator E k;' via a sequence of horizontal and vertical rotations obtained by
multiplications by the special permutation matrix \Pi:
The rotation operations correspond to the ' operator of the model for multilinear func-
tions. There are, however, two different kinds of rotations-horizontal and vertical-
due to the two-dimensional nature of the input, and the function h defining the behavior
of the function with respect to these rotations is not always easily computable
short of actually performing a matrix multiplication. We therefore exploit some additional
properties of the problem to come up with a set of conditions that are sufficient
for P to be computing matrix multiplication f . Let M 0
n denote the subgroup of Mn
that contains only matrices with columns all-zero.
Theorem 3.3. Let P be a program for f and ffl ! 1=8.
(a) Suppose P satisfies the following:
ffl.
Then the function g defined by g(X; Y
bilinear function on M 2
n , and g agrees with P
on at least 1 \Gamma 2ffl fraction of the inputs.
(b) Furthermore, suppose g satisfies the following conditions:
To be able to prove this theorem, we first need to show that the conditions
recounted have stronger implications than their statements. Then we will show that
these strengthened versions of the conditions imply Theorem 3.3.
First, we show that condition (2) implies a stronger version of itself:
Lemma 3.4. If condition (2) in Theorem 3.3 holds then g(E
Proof. We in fact show something stronger. We show that g(X; Y
all
Pr
\Theta g(X; Y
The second equality holds with probability by condition (2). All the rest
hold from linearity of g and f . The result follows since ffl ! 1=4. The lemma follows
since
n .
An immediate adaptation of the proof of Lemma 3.4 can be used to extend condition
(3) to hold for all inputs.
Next, we show that the linearity of g makes it possible to conclude from hypothesis
(4) that g is associative.
Lemma 3.5. If condition (4) in Theorem 3.3 holds then g is always associative.
Proof.
Pr
\Theta
The first equality holds from the linearity of g after expanding X;Y; Z as
respectively. The second one is true by the condition
8ffl. The last one is a recombination of terms using linearity.
We now have the tools to prove Theorem 3.3.
Proof. The bilinearity of g follows from the proof of Theorem 3.1.
From Lemmas 3.4 and 3.5, we have that condition (2) can be extended such that
conditions (3) and (4) on
hold for all inputs.
To show that these properties are sufficient to identify g as matrix multiplication,
note that from the multilinearity of g we can write,
1-i;j-n
1-k;'-n
1-i;j;k;'-n
If implies that g is the
same as f . Now, using our assumptions, we proceed to show the former holds:
The first equality is just a rewriting of the two generators in terms of other generators.
The second one follows from the strengthening of condition (3) that g computes f
whenever one of its arguments is equal to a power of \Pi. The third one follows from
associativity of g, and the fourth one holds because g is the same as f when the first
input is a power of \Pi and because of rewriting of E k+j \Gamma2;' . The fifth equality is true
because g computes f correctly when its first argument is E i;1 (as the consequence of
condition (2), see Lemma 3.4). The last one is a rewriting of the previous equality,
using the associativity of multiplication. Therefore, g is the same function as f .
We now present the test for associativity:
UN, S. R. KUMAR, AND D. SIVAKUMAR
Associativity Test:
Repeat O( 1
ae ) times
Pick X;Y; Z 2R Mn
Verify P sc (X; P sc (Y;
Reject if the test fails
A self-tester can be built by testing conditions (1), (2), (3), and (4), which correspond
to the Property Test the Basis Test, the Inductive Test and the Associativity
Test respectively. Note that testing conditions (2) and (3) involve knowing the value
of f at random inputs. These inputs, however, come from a restricted subspace which
makes it possible to compute f both easily and efficiently. The following theorem is
immediate.
Theorem 3.6. For any ae ! 1 and ffl ! 1=8, there is an ffl-self-tester for matrix
multiplication that succeeds with probability at least 1 \Gamma ae.
4. Nonlinear Functions. In this section, we consider nonlinear functions.
Specifically, we deal with exponentiation and constant degree polynomials in the ring
of polynomials over the finite fields Z p . It is obvious that exponentiation and constant
degree polynomials are clearly defined over this ring.
4.1. Constant Degree Exponentiation. We first consider the function
q d for some d (that is, raising a polynomial to the d-th power). Suppose a program
P claims to perform this exponentiation for all degree n polynomials q 2 Pn ' K [x].
Using the low-degree test of Rubinfeld and Sudan [19] (see also [14]) we can first test
if the function computed by P is close to some degree d polynomial g. As before,
using the self-corrected version P sc of P , we can also verify that g(e 1
The induction identity applies, and one can test whether
P satisfies this property on most inputs. Now it remains to show that this implies
We follow a strategy similar to the case of linear
functions, this time using the Lagrange interpolation formula as the robust property
that identifies a degree d polynomial. We note that this idea is similar to the use of
the interpolation formula by Gemmell, et al. [14], which extends the [5] result from
linear functions to low-degree polynomials. Before proceeding with the proof, we state
the following fact concerning the Lagrange interpolation identity.
Fact 4.1. Let g be a degree d polynomial. For any q 2 Pn , if are
distinct elements of Pn ,
Y
; and also
Y
The self-tester for comprises the following tests:
Degree Test:
Verify P is close to a degree d polynomial g (low-degree test)
Reject if the test fails
Basis Test:
Verify P sc
Inductive Test:
Repeat O( 1
ae ) times
Pick ff 2R V
Verify P sc
Reject if the test fails
Let fi denote the probability that the d random choices from the domain produce
distinct elements. We will assume that the domain is large enough so that fi is close
to 1.
Assume that P passes the Degree Test and P sc passes the Basis Test that is,
agrees with some degree-d polynomial g on most inputs. We note that the low-degree
of test of [19] makes O((1=ffl) log(1=ae)) calls to render a decision with confidence
only O((1=ffl) log(1=ae)) calls to compute g
correctly with probability (ae=3). Below we sketch the proof that if ffl
and P sc passes the Inductive Test then g satisfies
that so the time taken by the tester is only \Theta(d) (when ae is a constant).
Pr
a
a
a
Here a
The first equality is Fact 4.1, and applies since
g has been verified to be a degree d polynomial. Since the q i 's are uniformly and
identically distributed, by Inductive Test the second equality fails with probability
1)ffl. The third equality is just rewriting, and the fourth equality is due to
Fact 4.1 (the interpolation identity), which can be applied so long as the q i 's are
distinct, an event that occurs with probability fi. Since the equality
holds independent of q i 's, if ffl holds with probability 1.
Theorem 4.2. The function has an O(1=d)-self-tester
that makes O(d) queries.
4.2. Constant Degree Polynomials. Next we consider extending the result of
x4.1 to arbitrary degree d polynomials f : Pn ! P nd . Clearly the low-degree test and
the basis test work as before. The interpolation identity is valid, too. The missing
ingredient is the availability of an identity like "f which, as we have
shown above, is a robust property that can be efficiently tested. We show how to get
UN, S. R. KUMAR, AND D. SIVAKUMAR
around this difficulty; this idea is based on a suggestion due to R. Rubinfeld [private
communication].
nd is a degree d polynomial (eg.,
suppose a program P purports to compute f . Our strategy is to design a self-corrector
R for P and to then estimate the fraction of inputs q such that P (q) 6= R(q). The
difficulty in implementing this idea by directly using the random self-reducibility of
f is that the usefulness of the self-corrector (to compute f correctly on every input)
depends critically on our ability to certify that P is correct on most inputs. Since
checking whether P is correct on most inputs is precisely the task of self-testing, we
seem to be going in cycles.
To circumvent this problem, we will design an intermediate multiplication program
Q that uses P as an oracle. To design the program Q, we prove the following
technical lemma that helps us express d-ary multiplication in terms of f-that is, we
establish a reduction from the multilinear function
to the nonlinear function
f . This reduction is a generalization to degree d of the elementary polarization identity
slightly stronger in that it works for arbitrary
polynomials of degree d, not just degree-d exponentiation.
Lemma 4.3. For x 2 f0; 1g d , let x i denote the i-th bit of x. For any polynomial
of degree d,
x2f0;1g d
Y
G
d
Y
Using the reduction given by Lemma 4.3, we will show how to construct an ffl-self-
tester T for f (for following the outline sketched.
(1) First we build a program Q that performs c-ary multiplication for any c - d
d, we can simply multiply by extra 1's). The program Q is then self-tested
efficiently (without the generator bottleneck) by using a (1=2 d+1 )-self-tester for the
d-variate multilinear multiplication function from x3. The number of queries made to
P in this process is O(1), where the constant depends on d (the degree of f) but not
on n (the dimensionality of the domain of f ). Thus if Q passes this self-testing step,
then it computes multiplication correctly on all but 1=2 d+1 fraction of the inputs. If
Q fails the self-testing process, the self-tester T rejects.
(2) Next we build a reliable program Q sc that self-corrects Q using the random
self-reducibility of the multilinear multiplication function. That is, Q sc can be used to
compute c-ary multiplication (for any c - d) correctly for every input with probability
at least 1 \Gamma ae for any constant ae ? 0. In particular, by making O(2 d log d) calls to
(and hence O(2 2d log d) calls to P ), Q sc can be used to compute multiplication
correctly for every input with probability at least 1 \Gamma (1=10d).
(3) Next, we use Q sc to build the program R that computes f(q) in the straight-forward
way by using Q sc to compute the d required multiplications. If Q sc computes
multiplication correctly with probability correctly for
any input with probability at least 0:9.
Finally, T randomly picks O((1=ffl) log(1=ae)) many samples q and checks
if outputs PASS iff P all the chosen values of q.
It is easy to see that if P computes f correctly on all inputs, the self-tester T will
output PASS with probability one. For the converse, suppose that
outputs PASS. We will upper bound the probability of this event
by ae.
Since Q passes the self-testing step (Step (1)), it computes multiplication correctly
on all but 1=2 d+1 fraction of the inputs, and therefore, the the use of the self-corrector
Q sc as described in Step (2) is justified. This, in turn, implies the guarantee made of
R in Step (3): for every input q, with probability at least 0:9. In Step
(4), the probability that P (q) 6= R(q) for a single random q is at least (0:9)ffi. The
probability that P for every random input q chosen in Step (4) is therefore
at most (1 \Gamma (0:9)ffi)
Thus the probability that T outputs PASS, given that Pr q [P (q) 6= f(q)] ? ffl, is at
most ae. The following theorem is proven, modulo the proof of Lemma 4.3.
Theorem 4.4. The function f(q), where f is a polynomial in q 2 Pn of degree
d, has an O(1=2 d )-self-tester that makes O(2 d ) queries.
Even though our self-tester makes O(2 d ) queries to test degree-d exponentiation, the
number of queries is independent of n, the dimensionality of the domain. Thus, our
self-tester is attractive if n is large and d is small. In particular, in conjunction with
the testers for finite field arithmetic described in x3.1, the self-testers described here
help us to efficiently self-test constant degree polynomials on finite field extensions of
large dimension.
It remains to prove Lemma 4.3. This lemma is a direct corollary of the following
lemma, which illustrates a method to express d-ary multiplication in terms of f . The
proof of the next lemma is given in the Appendix.
Lemma 4.5. Let d be distinct variables. For x 2 f0; 1g d , let x i denote
the i-th bit of x. Then
x2f0;1g d
Y


Appendix

. Proof of Lemma 2.4 and Lemma 4.5.
Lemma 2.4. If q is a polynomial in x of degree - k, then
Proof. By induction on k. The base case obviously true. Let k ? 0, we
have
and since differentiation is linear, we have
Since the first term (i = 0) in the first sum vanishes, and since i
\Delta , the first sum evaluates to
which 1)!q by the inductive hypothesis. Hence it suffices to
show that the second sum evaluates to 0. This summation can be written
as
tity, this sum can be split into the terms
xD(q)). The second term can be seen
UN, S. R. KUMAR, AND D. SIVAKUMAR
to be (\Gammax)k!D(q) using the induction hypothesis. The first and third terms can be
combined to obtain k!(xD(q)) again using the induction hypothesis. Thus, the entire
Lemma 4.5. Let d be distinct variables. For x 2 f0; 1g d , let x i denote
the i-th bit of x. Then
x2f0;1g d
Y
Proof. The proof uses the Fourier Transform on the boolean cube f0; 1g d (us-
ing the standard isomorphism between f0; 1g d and Z d
denote the space of
functions from Z d
into C . F is a (finite) vector space of functions of dimension 2 d .
Define the inner product between functions f;
x f(x)g(x).
For
define the function - ff : Z d
x i and ff i denote the i-th bits, respectively, of x and ff. It is easy to check that
whence every - ff is a character of Z d
. Furthermore, it is
easy to check that h- ff Therefore, the
characters - ff form an orthonormal basis of F , and every function f : Z d
unique expansion in this basis as
ff
f ff - ff . This is called the Fourier transform
of f , and the coefficients b
f ff are called the Fourier coefficients of f ; by the orthonormality
of the basis, b
h- ff ; fi. An easy property of the Fourier transform is that
for ff 6= 0 d ,
(in fact, this is true for any non-trivial character of any
group).
For the proof of the lemma, we note that it suffices to prove the lemma for all
complex numbers p i . Fix a list of complex numbers define the function
. Then the left hand side of the statement of the
lemma is just 2 d b
Thus:
x2Z d/ d
Y
f ff
x
x
0-n1 ;:::;n d -c
Y
0-n1 ;:::;n d -c
Y
x
d
Y
0-n1 ;:::;n d -c
Y
x
d
Y
The innermost sum is zero if ff
every i, that is, n d, this is impossible,
since
d, then the only way this can happen is if
otherwise, for some i, n i ? 1, and since
i, it is easy to see that we have 2 d b

Acknowledgments

. We are very grateful to Ronitt Rubinfeld for her valuable
suggestions and guidance. We thank Manuel Blum and Mandar Mitra for useful
discussions. We thank Dexter Kozen for his comments. We are grateful to the two
anonymous referees for valuable comments that resulted in many improvements to our
exposition. The idea of describing the proof of Lemma 4.5 using Fourier transforms
is also due to one of the referees.



--R

Checking approximate computations over the reals

Hiding instances in multioracle queries
Designing programs that check their work

A theory of testing meets a test of theory
Reflections on the Pentium division bug
Functional Equations and Modeling in Science and Engineer- ing
A note on self-testing/correcting methods for trigonometric functions

Locally random reductions in interactive complexity theory
Approximating clique is almost NP-complete
Fast probabilistic algorithms


On self-testing without the generator bottleneck
New directions in testing
Testing polynomial functions efficiently and over rational do- mains
Robust characterizations of polynomials with applications to program testing
A Mathematical Theory of Self-Checking
Robust functional equations with applications to self-testing/ correcting
On the role of algebra in the efficient verification of proofs
--TR

--CTR
M. Kiwi, Algebraic testing and weight distributions of codes, Theoretical Computer Science, v.299 n.1-3, p.81-106,
Marcos Kiwi , Frdric Magniez , Miklos Santha, Exact and approximate testing/correcting of algebraic functions: a survey, Theoretical aspects of computer science: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2002
program correctness;generator bottleneck;self-testing