Checking Approximate Computations of Polynomials and Functional Equations.
A majority of the results on self-testing and correcting deal with programs which purport to compute the correct results precisely. We relax this notion of correctness and show how to check programs that compute only a numerical approximation to the correct answer. The types of programs that we deal with are those computing polynomials and functions defined by certain types of functional equations.  We present results showing how to perform approximate checking, self-testing, and self-correcting of polynomials, settling in the affirmative a question raised by [P. Gemmell et al., Proceedings of the 23rd ACM Symposium on Theory of Computing, 1991, pp. 32--42; R. Rubinfeld and M. Sudan, Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, Orlando, FL, 1992, pp. 23--43; R. Rubinfeld and M. Sudan, SIAM J. Comput., 25 (1996), pp. 252--271]. We obtain this by first building approximate self-testers for linear and multilinear functions.  We then show how to perform approximate checking, self-testing, and self-correcting for those functions that satisfy addition theorems, settling a question raised by [R. Rubinfeld, SIAM J. Comput., 28 (1999), pp. 1972--1997]. In both cases, we show that the properties used to test programs for these functions are both robust (in the approximate sense) and stable. Finally, we explore the use of reductions between functional equations in the context of approximate self-testing. Our results have implications for the stability theory of functional equations.
Introduction
Program checking was introduced by Blum and Kannan [BK89] in order to allow one to use
a program safely, without having to know apriori that the program is correct on all inputs.
Related notions of self-testing and self-correcting were further explored in [BLR93, Lip91].
These notions are seen to be powerful from a practical point of view (c.f., [BW94]) and from a
theoretical angle (c.f., [AS92, ALM + 92]) as well. The techniques used usually consist of tests
performed at run-time which compare the output of the program either to a predetermined
value or to a function of outputs of the same program at dierent inputs. In order to apply
these powerful techniques to programs computing real valued functions, however, several
issues dealing with precision need to be dealt with. The standard model, which considers an
output to be wrong even if it is o by a very small margin, is too strong to make practical
sense, due to reasons such as the following. (1) In many cases, the algorithm is only intended
to compute an approximation, e.g., Newton's method. (2) Representational limitations and
roundo/truncation errors are inevitable in real-valued computations. (3) The representation
of some fundamental constants (e.g., inherently imprecise.
The framework presented by [GLR accommodates these inherently inevitable
or acceptably small losses of information by overlooking small precision errors while
detecting actual \bugs", which manifest themselves with greater magnitude. Given a function
f , a program P that purports to compute f , and an error bound , if jP (x) f(x)j
(denoted P (x)  f(x)) under some appropriate notion of norm, we say P (x) is approximately
correct on input x. Approximate result checkers test if P is approximately correct
for a given input x. Approximate self-testers are programs that test if P is approximately
correct for most inputs. Approximate self-correctors take programs that are approximately
correct on most inputs and turn them into programs that are approximately correct on every
input.
Domains. We work with nite subsets of xed point arithmetic that we refer to as nite
rational domains. For n; s
s
l is the
precision. We allow s and n to vary for generality. For a domain D, let D + and D denote
the positive and negative elements in D.
Testing using Properties. There are many approaches to building self-testers. We
illustrate one paradigm that has been particularly useful. In this approach, in order to test if
a program P computes a function f on most inputs, we test if P satises certain properties
of f .
As an example, consider the function and the property \f(x
that f satises. One might pick random inputs x and verify that P 2.
Clearly, if for some x, P incorrect. The program, however,
might be quite incorrect and still satisfy most choices of random
inputs. In particular, there exists a P (for instance, P
high probability, P satises the property at random x and hence will pass the test, and (ii)
there is no function that satises the property for all x such that P agrees with this function
on most inputs. Thus we see that this method, when used naively, does not yield a self-tester
that works according to our specications. Nevertheless, this approach has been used as a
good heuristic to check the correctness of programs [Cod91, CS91, Vai93].
As an example of a property that does yield a good tester, consider the linearity property
only by functions mapping D n;s to R of the form
random sampling, we conclude that the program P satises this property
for most x; y, it can be shown that P agrees with a linear function g on most inputs [BLR93,
Rub94]. We call the linearity property, and any property that exhibits such behavior, a
robust property.
We now describe more formally how to build a self-tester for a class F of functions that
can be characterized by a robust property. Our two-step approach, which was introduced in
[BLR93], is: (i) test that P satises the robust property (property testing), and (ii) check if P
agrees with a specic member of F (equality testing). The success of this approach depends
on nding robust properties which are both easy to test and lead to ecient equality tests.
A property is a pair hI; E (n;s) i, consisting of an equation I f
the values of function f at various tuples of locations hx
over D k
(n;s) from which the locations are picked. The property hI; E (n;s) i is said to char-
We naturally extend the mod function to D n;s by letting xmodK stand for j modK
s , for x; K 2 D n;s ,
and
s ,
acterize a function family F in the following way. A function f is a member of F if and
only if I f that has non-zero measure under E (n;s) . For
instance, the linearity property can be written as I f
(n;s) is a distribution on hx 1 are chosen randomly
from some distribution 2 over the domain D (n;s) . In this case hI; E Lin
Rg, the set of all linear functions over D (n;s) . We will adhere to
this denition of a property throughout the paper; however, for simplicity of notation, when
appropriate, we will talk about the distribution and the equality together. For instance, it
is more intuitive to express the linearity property as f(x giving the
distributions of x; y, than writing it as a pair.
We rst consider robust properties in more detail. Suppose we want to infer the correctness
of the program for the domain D n;s . Then we allow calls to the program on a larger
domain D (n;s) , where is a xed function that depends on the structure of I.
Ideally, we would like (n; . But, for technical reasons, we
allow D (n;s) to be a proper, but not too much larger, superset of D n;s (in particular, the
description size of an element in D (n;s) should be polynomial in the description size of an
element in D n;s ). 3
To use a property in a self-tester, one must prove that the property is roubust. Informally,
the )-robustness of the property hI; E (n;s) i implies that if, for a program P ,
I P with probability at least 1  when hx is chosen from
the distribution E (n;s) , then there is a function g 2 F that agrees with P on 1  fraction of
the inputs in D n;s . In the case of linearity, it can be shown that there is a distribution E Lin
11n;s
on 11n;s such that the property is (2; ; D 11n;s ; D n;s )-robust
for all  < 1=48 [BLR93, Rub94]. Therefore, once it is tested that P satises P
probability when the inputs are picked randomly from E Lin
11n;s ,
it is possible to conclude that P agrees with some linear function on most inputs from
2 For example, choosing x 1 and x 2 uniformly from D (n;s) suces for characterizing linearity. To prove
robustness, however, [Rub94] uses a more complicated distribution that we do not describe here.
3 Alternatively, one could test the program over the domain D n;s and attempt to infer the correctness of
the program on most inputs from Dn 0 ;s 0
, where Dn 0 ;s 0
is a large subdomain of D n;s .
D n;s . A somewhat involved denition of robust is given in [Rub94]. Given a function
such that for all n; s, D n;s is a large enough subset of D (n;s) , in this paper we say that a
property is robust if: for all 0 <  < 1, there is an  such that for all n; s the property is
)-robust.
We now consider equality testing. Recall that once it is determined that P satises
the robust property, then equality testing determines that P agrees on most inputs with a
specic member of F . For instance, in the case of linearity, to ensure that P computes the
specic linear function most inputs, we perform the equality test which ensures
that
s
s
for most x. Neither the property test nor the equality test on its
own is sucient for testing the program. However, since x is the only function that
satises both the linearity property and the above equality property, the combination of the
property test and the equality test can be shown to be sucient for constructing self-testers.
This combined approach yields extremely ecient testers (that only make O(1) calls to
the program for xed  and ) for programs computing homomorphisms (e.g., multiplication
of integers and matrices, exponentiation, logarithm). This idea is further generalized in
[Rub94], where the class of functional equations called addition theorems is shown to be useful
for self-testing. An addition theorem is a mathematical identity of the form 8x;
Addition theorems characterize many useful and interesting mathematical
functions [Acz66, CR92]. When G is algebraic, they can be used to characterize families of
functions that are rational functions of x, e cx , and doubly periodic functions (see Table 1 for
examples of functional equations and the families of functions that they characterize over the
reals). Polynomials of degree d can be characterized via several dierent robust functional
equations (e.g., [BFL91, Lun91, ALM
Approximate Robustness and Stability. When the program works with nite
precision, the properties upon which the testers are built will rarely be satised, even by a
program whose answers are correct up to the required (or hardware-wise maximal) number
of digits, since they involve strict equalities. Thus, when testing, one might be willing to
pass programs for which the properties are only approximately satised. This relaxation in
the tests, however, leads to some diculties, for in the approximate setting (1) it is harder
cot Ax f(x)+f(y) 2f(x)f(y) cos a
sin Ax
sin Ax+a
f(x)+f(y) 2f(x)f(y) cosh a
sinh Ax
sinh Ax+a
Ax
f(x)+f(y)+2f(x)f(y) cosh a
sinh Ax
sinh Ax+a
Ax
A
x

Table

1: Some Addition Theorems of the form f(x
to analyze which function families are solutions to the robust properties, and (2) equality
testing is more dicult. For instance, it is not obvious which family of functions would satisfy
both (approximate linearity property) and
s
s
for all x 2 D (n;s) . (approximate equality property).
To construct approximate self-testers, our approach is to rst investigate a notion of
approximate robustness of the property to be used. We rst require a notion of distance
between two functions.
Denition 1 (Chebyshev Norm) For a function f on a domain D,
fjf(x)jg:
When the domain is obvious from the context, we drop it. Given functions f; g, the distance
between them is kf gk. Next, we dene the approximation of a function by another:
Denition 2 The function P (; )-approximates f on domain D if kP fk   on at
least 1  fraction of D.
Approximate robustness is a natural extension of the robustness of a property. We say that a
program satises a property approximately if the property is true of the program when exact
equalities are replaced by approximate equalities. Once again consider the linearity property
and a program P that satises the property approximately (i.e., P
but an  fraction of the choices of hx
(n;s) . The approximate
robustness of linearity implies that there exists a function g and a choice of  0 ;  00 such that
2)-approximates P on D n;s
In general, we would like to dene approximate robustness of a property
as the following: If a program P satises the equation I approximately on most
choices of inputs according to the distribution E (n;s) , then there exists a function g that (i)
I approximately on all inputs chosen according to E n;s (ii) approximates P on most
inputs in D n;s . The function  relating the distributions used for describing the behaviors of
P and G depends on I, but is not required to be uniformly Turing-computable.
We now give a formal denition of approximate robustness:
Denition 3 (Approximate Robustness) Let hI; E (n;s) i characterize the family of functions
F over the domain D (n;s) . Let F 0 be the family of functions satisfying I approximately
on all inputs chosen according to E n;s . A property hI; E (n;s) i for a function family F 0 is
)-approximately robust if 8P; Pr x 1 ;:::;x k 2E (n;s)
implies there is a )-approximates P on D n;s and I g
Once we know that the property is approximately robust, the second step is to analyze
the stability of the property, i.e., to characterize the set of functions F 0 that satisfy the
property approximately and compare it to F , the set of functions that satisfy the property
exactly (Hyers-Ulam stability). In our linearity example, the problem is the following: given
satisfying g(x in the domain, is there a homomorphism h
that with  0 depending only on  and not on the size of the domain?
If the answer is armative, we say that the property is stable. In the following denition,
Denition 4 (Stability) A property hI; E n;s i for a function family F is (D n;s ; D n 0 ;s
stable if 8g that satises I g  0 for all tuples with non-zero support according to E n;s , there
is a function h that satises I support according to E n 0 ;s 0
with kh gkD n 0 ;s 0
If a property is both approximately robust and stable, 4 then it can be used to determine
whether P approximates some function in the desired family. Furthermore, if we have a
method of doing approximate equality testing, then we can construct an approximate self-
tester.
Previous Work. Previously, not many of the known checkers have been extended to
the approximate case. Often it is rather straightforward to extend the robustness results to
show approximate robustness. However, the diculty with extending the checkers appears
to lie in showing the stability of the properties. The issue is rst mentioned in [GLR
where approximate checkers for mod, exponentiation, and logarithm are constructed. The
domain is assumed to be closed in all of these results. A domain is said to be closed under
an operation if the range of the operation is a subset of the domain. For instance, a nite
precision rational domain is not closed under addition. In [ABC + 93] approximate checkers for
sine, cosine, matrix multiplication, matrix inversion, linear system solving, and determinant
are given. The domain is assumed to be closed in the results on sine and cosine. In [BW95]
an approximate checker for
oating-point division is given. In [Sud91], a technique which
uses approximation theory is presented to test univariate polynomials of degree at most 9.
It is left open in [GLR whether the properties used to test
polynomial, hyperbolic, and other trigonometric functions can be used in the approximate
setting. For instance, showing the stability of such functional equations is not obvious; if
the functional equation involves division with a large numerator and a small denominator,
a small additive error in the denominator leads to a large additive error in the output.
There has been signicant work on the stability of specic functional equations. The
stability of linearity and other homomorphisms is addressed in [Hye41, For80, FS89, Cho84].
The techniques used to prove the above results, however, cease to apply when the domain
is not closed. The stronger property of stability in a non-closed space, called local stability,
4 The associated distribution needs to be sampleable
is addressed by Skof [Sko83] who proves that Cauchy functional equations are locally stable
on a nite interval in R. The problem of stability of univariate polynomials over continuous
domains is rst addressed in [AB83] and the problem of local stability on R is solved in
[Gaj90]. See [For95] for a survey. These results do not extend in an obvious way to nite
subsets of R, and thus cannot be used to show the correctness of self-testers. For those
that can be extended, the error bounds obtained by naive extensions are not optimal. Our
dierent approach allows us to operate on D n;s and obtain tight bounds.
Results. In this paper, we answer the questions of [GLR
in the armative, by giving the rst approximate versions of most of their testers. We rst
present an approximate tester for linear and multilinear functions with tight bounds. These
results apply to several functions, including multiplication, exponentiation, and logarithm,
over non-closed domains. We next present the rst approximate testers for multivariate poly-
nomials. Finally, we show how to approximately test functions satisfying addition theorems.
Our results apply to many algebraic functions of trigonometric and hyperbolic functions
(e.g., sinh, cosh). All of our results apply to non-closed discrete domains.
Since a functional equation over R has more constraints than the same functional equation
over D n;s , it may happen that the functional equation over R characterizes a family of
functions that is a proper subset of the functions characterized by the same functional
equation over D n;s . This does not limit the ability to construct self-testers for programs
for these functions, due to the equality testing performed by self-testers.
To show our results, we prove new local stability results for discrete domains. Our techniques
for showing the stability of multilinearity dier from those used previously in that
(1) we do not require the domain to be discrete and (2) we do not require the range to
be a complete metric space. This allows us to apply our results to multivariate polynomial
characterizations. In addition to new combinatorial arguments, we employ tools from
approximation theory and stability theory. Our techniques appear to be more generally
applicable and cleaner to work with than those previously used.
Self-correctors are built by taking advantage of the random self-reducibility of polynomials
and functional equations [BLR93, Lip91] in the exact case. As in [GLR + 91], we employ a
similar idea for the approximate case by making several guesses at the answer and returning
their median as the output. We show that if each guess is within  of the correct answer
with high probability, then the median yields a good answer with high probability. To build
an approximate checker for all of these functions, we combine the approximate self-tester
and approximate self-corrector as in [BLR93].
Organization. Section 2 addresses the stability of the properties used to test linear
and multilinear functions. Using these results, Section 3 considers approximate self-testing
of polynomials. Section 4 addresses the stability and robustness of functional equations.
Section 5 illustrates the actual construction of approximate self-testers and self-correctors.
2 Linearity and Multilinearity
In this section, we consider the stability of the robust properties used to test linearity and
multilinearity over the nite rational domain D n;s . The results in this section, in addition
to being useful for the testing of linear and multilinear functions, are crucial to our results
in Section 3.
As in [GLR + 91], approximate robustness is easy to show by appropriately modifying the
proof of robustness [Rub94]. This involves replacing each exact equality by an approximate
equality and keeping track of the error accrued at each step of the proof. To show stability,
we use two types of bootstrapping arguments: the rst shows that an error bound on a small
subset of the domain implies the same error bound on a larger subset of the domain; the
second shows that an error bound on the whole domain implies a tighter error bound over
the same domain. These results can be applied to give the rst approximate self-testers for
several functions over D n;s including multiplication, exponentiation, and logarithm (Section
2.2).
2.1 Approximate Linearity
The following denes formally what it means for a function to be approximately linear:
Denition 5 (Approximate Linearity) A function g is -approximately linear on D n;s
Hyers [Hye41] and Skof [Sko83] obtain a linear approximation to an approximately linear
function when the domain is R. (See Appendix A for their approach). Their methods are
not extendible to discrete domains.
Suppose we dene h( 1
s ). In the 0-approximately linear case (exact linearity), since
s
s
s
s
s
s
by induction on the elements in D n;s , we
can show that This approach is typically used to prove the suciency of
the equality test. However, in the -approximately linear case for  6= 0, using the same
inductive argument will only yield a linear function h such that h( i
s
s
). This is
quite unattractive since the error bound depends on the domain size. Thus, the problem
of obtaining a linear function h whose discrepancy from g is independent of the size of the
domain is non-trivial.
In [GLR + 91], a solution is given for when the domain is a nite group. Their technique
requires that the domain be closed under addition, and therefore does not work for D n;s .
We give a brief overview of the scheme in [GLR + 91] and point out where it breaks down
for non-closed domains. The existence of a linear h that is close to g is done in [GLR
by arguing that if D is suciently large, then an error of at least  at the maximum error
point x  would imply an even bigger error at 2x  , contradicting the maximality assumption
about error at x  . Here, the crucial assumption is that x 2 D implies 2x 2 D. This step
fails for domains which are not closed under addition.
Instead, we employ a dierent constructive technique to obtain a linear h on D n;s given a
-approximately linear g. Our technique yields a tight bound of 2 on the error e  h g
(instead of 4 in [Sko83]) and does not require that the domain be closed under addition.
It is important to achieve the best (lowest) constants possible on the error, because these
results are used in Section 3.2 where the constants aect the error in an exponential way.
The following lemma shows how to construct a linear function h that is within
of a -approximately linear function g in D
n;s .
Lemma 6 Let g be a -approximately linear function on D
n;s , and let h be linear on D n;s .
s
Proof.
We prove by contradiction that 8x 2 D
argument can
be made to show that e(x)
Recall that n
s
is the greatest positive element of the domain, and note that e is a -
approximately linear function. Assume that there exists a point in D
n;s with error greater
be the maximal such element. p has to lie between n
2s
and n
s
, otherwise
n;s would have error greater than 2 contradicting the maximality of p. Let
s
p. Then, e(q)
s
Also, for any x 2 (p; n
s
n;s ,
by denition of p, e(x) . Note that any such x can be written as
To satisfy the approximate linearity property that e(x 0 must
have error strictly less than + .
We now know that the points in the interval (0; q] have error strictly less than 2+  (in
that the point q itself has error strictly less than . Putting
these two facts and approximate linearity together, and since any x 2 (q; 2q] can be written
as q]; we can conclude that at any point in (q; 2q], the error is at most
2+ . Now we can repeat the same argument by taking y from (0; 2q] rather than (0; q] to
bound the error in the interval (0; 3q] by 2 . By a continuing argument, eventually the
interval contains the point p, which means that p has error at most 2+. This contradicts
our initial assumption that e(p) was greater than 2
In addition, since e(0)
We now generalize the error bound on D
n;s to D n;s .
Lemma 7 If a function g is -approximately linear on D n;s , with h and e are dened as
before, and if je( n
Proof. Observe that if the error is upper bounded by  in [0; n
s
2s
, so that e(2x)  . Also, if je(x)j   then je( x)j
n;s . We will bound the error in D n;s
rst by 3 . From the above observations, we have e(x)  4
2s
2s
Assume that 9x 2 D n;s such that be the minimal such
point. Then p > n
2s
, otherwise the error at 2p would exceed 3 t be the point
with the highest error in D
n;s (maximal such one if there is a tie). We consider the possible
locations for t to bound e(t): (1) if t  n
2s
, then to ensure that e(2t)  e(t), e(t)  ;
2s
2s
therefore, to satisfy the bound above on e(t
2s
therefore to satisfy the bound above,
e(t)  =2   .
Regardless of where t lies, e(t)    +, hence the error in D
n;s is bounded by +.
However, e( n
s
s
n;s , this contradicts the
bound we established before. Therefore, there cannot be a point in D n;s with error greater
argument can be used to bound negative error.
Now we reduce the error bound to 2 + . Assume that p is the minimal point in D n;s
with error at least 2 + . The proof is similar to the previous stage, using the tighter
bound e(x)
2s
stay the same; for case (2)
we . Therefore, the error cannot exceed
s
which is a contradiction.
The following special case proves the stability result for linearity:
Corollary 8 The linearity property is (D n;s ; D n;s
Proof. Suppose function g is -approximately linear on D n;s . Set h( n
s
s
7. This uniquely denes a linear h with
The intuition that drives us to set h( n
s
s
) in the proof of Corollary 8 is as follows.
Consider the following function: g( n
s
s
s
integer part of number).
It is easy to see that g(x+y)  g(x)+g(y). If we set h( 1
s ), then we obtain h( n
s .
But kg hk is a growing function of n and so there is no way to bound the error at all points.
The following example shows that the error bound obtained in Corollary 8 using our
technique is tight: we have shown how to construct a linear function h so that kh gk
2. We now show that there is a function g that, given our method of constructing h,
asymptotically approaches this bound from below. Dene g as follows:
(3x=n It is easy to see that g
is -approximately linear: If x
Our construction sets 0, the zero
function. However, kg large enough n.
2.2 Approximate Multilinearity
In this section we focus our attention on multilinear functions. A multivariate function is
multilinear if it is linear in any one input when all the other inputs are xed. A multilinear
function of k variables is called a k-linear function. An example of a bilinear function is
multiplication, and bilinearity property can be stated concisely as
that distributive property of multiplication
with respect to addition is a special case of multilinearity.
A natural extension of this class of functions is the class of approximately multilinear
functions, which are formally dened below:
Denition 9 (Approximate Multilinearity) A k-variate function g is -approximately
k-linear on D k
n;s if it is -approximately linear on D n;s in each variable.
For instance, for is -approximately bilinear if 8x 1
Now we generalize Lemma 7 to -approximately k-linear functions. Let g be a -
approximately k-linear function and h be the multilinear function uniquely dened by the
condition h( n
s
s
g. e is a -approximately k-linear function.
Since g takes k inputs from D n;s , if we consider each input to g as a coordinate, the set
of all possible k-tuples of inputs of g form a (2n of dimension k.
We show that for any point
Theorem 10 The approximate k-linearity property is (D k
In other
words, if a function g is -approximately k-linear on D k
n;s , then there exists a k-linear h on
n;s such that kh gk  2k.
Proof. With h dened as above, e( n
s
First, we argue about points that have
one coordinate that is dierent from n
s
. Fix k 1 of the inputs to be n
s
(hard-wire into
g) and vary one (say x i ). This operation transforms g from a -approximately k-linear
function of x to a -approximately linear function of x i . By Lemma 7, this function
cannot have an error of more than 2 in D n;s . Therefore, je( n
s
s
s
s
s
. Next we consider points which have two coordinates that are dierent from n
s
Consider without loss of generality an input a; b; n
s
. By the result we just argued,
we know that e( n
s
s
s
2. By xing inputs 2 through k to be b; n
s
s
and
varying the rst input, by Lemma 7, we have je(a; b; n
s
)j  4 for any a 2 D n;s . Via
symmetric arguments, we can bound the error by 4 if any two inputs are dierent from n
s
Continuing this way, it can be shown that for all inputs, the error is at most 2k.
The following theorem shows that the error can be reduced to (1+) for any constant  > 0
by imposing the multilinearity condition on a larger domain D 0 and tting the multilinear
function h on D, where jD 0 d2k=e. Note that doubling the domain size only involves
adding one more bit to the representation of a domain element.
Theorem 11 For any  > 0, the approximate multilinearity property is (D k
))-stable.
Proof. By Theorem 10, g is 2k-close to a k-linear h on D 2kn=;s . For any x
we x all coordinates except x i and argue in the i-th coordinate as below.
For any D m;s , rst we show that if je(x)j Dm;s   then je(x)j D m=2;s
To
observe this, note that if x 2 D m=2;s , then 2x 2 D m;s . Therefore the function should satisfy
e(x)+e(x)  e(2x), which implies that je(x)j  (+)=2. Thus, in general, the maximum
error in D m=2 i ;s is  the error in D 2kn=;s is at most 2k, the error
in D n;s is at most (1 our choice of parameters. In the multilinear case, we can
make a similar argument by using points which have at least one coordinate x i within the
smaller half of the axis.
Note that, since h is multilinear, it is also symmetric.
To test programs purportedly computing polynomials, it is tempting to (1) interpolate the
polynomial from randomly chosen points, and then (2) verify that the program is approximately
equal to the interpolated polynomial for a large fraction of the inputs. Since a degree
d k-variate polynomial can have (d this leads to exponential running times.
Furthermore, it is not obvious how error bounds that are independent of the domain size
can be obtained.
Our test uses the same \evenly spaced" interpolation identity as that in [RS96]: for all

0: This identity is computed by the method of
successive dierences which never explicitly interpolates the polynomial computed by the
program, thus giving a particularly simple and ecient (O(d 2 ) operations) test.
We can show that the interpolation identity is approximately robust by modifying the
robustness theorem in [RS92]. (Section 3.3). Our proof of stability of the interpolation
identity (Section 3.2), however, uses a characterization of polynomials in terms of multilinear
functions that previously has not been applied to program checking. This in turn allows us
to use our results on the stability of multilinearity (Section 2.2) and other ideas from stability
theory. Section 3.4 extends these techniques to multivariate polynomials.
3.1 Preliminaries
In this section, we present the basic denitions and theorems that we will use. Dene
to be the standard forward dierence operator. Let
r d
d
z }| {
d

d
and r t 1
f(x). The following are simple facts concerning this operator.
Facts 12 The following are true for the dierence operator r:
1. r is linear: r(f
2. r is commutative: r t 1
, and
3. r t 1 +t 2
Let x [k] denote
z }| {
x. For any k-ary symmetric f , let f  diagonal
restriction. We use three dierent characterizations of polynomials [MO34, Dji69]. For the
following equations to be valid, all inputs to f must be from D. 5
Fact 13 The following are equivalent:
1. 8x 2 D;
d
a k x k ,
2.
3. there exist symmetric k-linear functions F k , 0  k  d such that 8x 2 D;
d
F
The following denitions are motivated by the notions of using evenly and unevenly spaced
points in interpolation.
Denition 14 (Strong Approximate Polynomial) A function g is called strongly -
approximately degree d polynomial if 8x; t
g(x)j  .
Denition 15 (Weak Approximate Polynomial) A function g is called weakly -approximately
degree d polynomial if 8x; t such that n < x
t g(x)j  .
3.2 Stability for Polynomials
First, we prove that if a function is strongly -approximately polynomial then there is a
polynomial that (2 d lg d ; 0)-approximates it. Next, we show that if a function is weakly
approximately polynomial on a domain, then there is a coarser subdomain on which the
function is strongly approximately polynomial. Combining these two, we can show that if
a function is weakly approximately polynomial on a domain, then there is a subdomain on
5 Due to the denition of the r operator, the inputs may sometimes slip outside the domain. Then, it is
not stipulated that the equation must hold.
which the function approximates a polynomial. By using Theorem 11, we can bring the
above error arbitrarily close to  by assuming the hypothesis on a large enough domain. In
order to pass programs that err by at most  0 , we need to set   (d
Strongly Approximate Case. One must be careful in dening polynomial h that is
close to g. For instance, dening h based on the values of g at some d points will not
work. We proceed by modifying techniques in [AB83, Gaj90], using the following fact:
Fact 16 If a function f is symmetric and k-linear, then r t 1 ;:::;t d f
The following theorem shows the stability of the strong approximate polynomial property.
Theorem 17 The strong approximate polynomial property is (D n(d+2);s ; D n;s
stable. In other words, if g is a strongly -approximately degree d polynomial on D n(d+2);s ,
then there is a degree d polynomial h d such that kg h d k Dn;s  O(2 d lg d ).
Proof. The hypothesis that g is a strongly -approximately degree d polynomial on
D n(d+2);s and the fact that x+t 1
. The rest of the proof uses this \modied hypothesis" and works with
D n;s .
We induct on the degree. When by the modied hypothesis, we have 8x; t 2
constant, we are done.
Suppose the lemma holds when the degree is strictly less than d + 1. Now, by the
modied hypothesis, we have Using Fact 12 and
then our modied hypothesis, we have jr t 1 +t 0
By symmetry of the dierence operator, we have in eect a -
approximate symmetric d-linear function on D n;s , say G(t
?? on multilinearity guarantees a symmetric d-linear H with kG Hk  2d. Let
d (x) for x 2 D n;s .
Now, we have 8x; t
d (x))j (denition of g 0 )
d (x)j (triangle inequality)
d (x)j (denition of r)
d (x)j (denition of G)
(denition of H d )
(modied hypothesis on g)
Now we apply the induction hypothesis. g 0 satises the hypothesis above for d and larger
error  so by induction, we are guaranteed the existence of a degree d 1
polynomial h d 1 such that kg 0 h d 1 k  e d 1  0 . Set h
d . By Fact 13 about
the characterization of polynomials, h d is a degree d polynomial. Now, e
Unwinding the recurrence, the nal error kg h d
Weakly Approximate Case. We rst need the following useful fact [Dji69] which
helps us to go from equally spaced points to unequally spaced points:
Fact
d
d
Using this fact, we obtain the following theorem. Let dg.
Theorem 19 If g is weakly (=2 d+1 )-approximately degree d polynomial on D n(d+1);s(d+1) ,
then g is strongly -approximately degree d polynomial on D n;s .
Proof. For we have by our choice of
parameters that t 0
Therefore,
jr d+1
3.3 Approximate Robustness for Polynomials
This section shows that the interpolation equation for degree d polynomials is in some
sense, approximately robust. All the results in this subsection are modications of the
exact robustness of polynomials given in [RS92]. Let
d+1
. To self-test P on
D n;s , we use the following domains. (These domains are used for technical reasons that will
become apparent in the proofs of the theorems in this section.) We use Pr x2D [] to denote
the probability of an event when x is chosen uniformly from domain D.
1. D (d+2)n;s
2.
3.
All assume that P satises the following properties (which can
be tested by sampling):
1. Pr
2. for each 0  j  d
3. for each 0
f
We obtain the following theorem that shows the
approximate robustness of polynomials. Let E (n;s) be the distribution that
ips a fair three-sided
die and on outcome i 2 f1; 2; 3g, chooses inputs according to distribution given in the
(i)-th equation above. Let D (n;s) be the union of the domains used in the above properties.
Theorem 20 The interpolation equation, where inputs are picked according to the distribution
)-approximately robust.
The rest of this section is devoted to proving the above theorem.
By Markov's inequality, g's denition, and the properties of P , it is easy to show that P
2)-approximates g:
Theorem 21 If program P satises the above three properties, then, for all
2.
Now, we set out to prove that g is a weakly approximate polynomial. Let (p
otherwise. For two domains A; B, subsets of a universe X , let
call the domains -close if (A; B)  1 . The
following fact is simple:
Fact 22 For any x 2 D (d+2)n;s , the domains T j and fx are
For any x, the domains T ij and fx are
The following lemma shows that, in some sense, g is well-dened:
Lemma 23 For all x 2 D (d+2)n;s , Pr
Proof. Consider l . For a xed 0  j  d using
properties of P and T jk and fx+jt are  2 -close (Fact 22), we get Pr[P
Summing over all 0  noting that
Using Lemma 45, we can
show that with a relaxation of twice the error, this probability lower bounds the probability
in the rst part of the lemma. The second part of the lemma follows from the rst via a
simple averaging argument.
Now, the following theorem completes the proof that g is a weakly approximate degree d
polynomial.
Theorem 24 For all x 2 D (d+2)n;s , 8i; Pr
[jr d+1
Proof. Theorem 21, Lemma 23 and the closeness of T ij and fx imply that
Summing the latter expression and putting together, we have the rst part of the lemma.
The second part follows from the rst part and the fact that T j and ft are
For an appropriate choice of ;  1 ;  2 , we have a g that is weakly (2 d+3 )-approximately
degree d polynomial on D n;s with g (; 2)-approximating P on D n;s .
3.4 Multivariate Polynomials
The following approach is illustrated for bivariate polynomials. We can easily generalize this
to multivariate polynomials. It is easy to show that the approximate robustness holds when
the interpolation equation ([RS96]) is used as in Section 3.3.
An axis parallel line for a xed y (horizontal line) is the set of points l
Zg. A vertical line is dened analogously. As a consequence of approximate robustness,
we have a bivariate function g(x; y) that is a strongly approximately degree d polynomial
along every horizontal and vertical line. We use this consequence to prove stability.
The characterization we will use is: f(x; y) is a bivariate polynomial (assume degree in
both x and y is d) if and only if there are d
where the range is the space of all (degree d) univariate polynomials in x.
For each value of y, g y (x) is a strongly approximately degree d polynomial. Using the
univariate case (Theorem 17), there is an exact degree d polynomial P y (x) such that for
all x, g(x; y)  2 d lg d  P y (x). Construct the function g 0 (x;
Now, for a xed x (i.e., on vertical line) for any y, using r t 1 ;:::;t d+1
g(x; y)  0, we have
is a bivariate function where along every horizontal
line, it is an exact degree d polynomial and along every vertical line, it is a strongly  0 -
approximate degree d polynomial. Interpreting g 0 (x; y) as g 0
x (y) and using the same idea
as in univariate case, we can conclude that r(t is a symmetric
approximate d-linear function (here, we used the fact that g 0
[x]). The rest of the
argument in Theorem 17 goes through because our proofs of approximate linearity (Lemma
and multilinearity (Theorem 10) assume that the range is a metric space (which is true for
PD [x] with, say, the Chebyshev norm). The result follows from the above characterization
of bivariate polynomials.
4 Functional Equations
Extending the technique in Lemma 7 to addition theorems f(x
straightforward, since G can be an arbitrary function. In order to prove approximate robustness
(Section 4.3), several related properties of G are required. Proving that G satises each
individual one is tedious; however, the notion of modulus of continuity from approximation
theory gives a general approach to this problem. We show that bounds on the modulus of
continuity imply bounds on all of the quantities of G that we require. The stability of G is
shown by a careful inductive technique based on a canonical generation of the elements in
D n;s (Section 4.2). The scope of our techniques is not only limited to addition theorems; we
also show that Jensen's equation is approximately robust and stable. (Section 4.2.4)
4.1 Preliminaries
For addition theorems, we can assume that G is algebraic and a symmetric function (the
latter is true in general under some technical assumptions as in [Rub94]). We need a notion
of \smoothness" of G. The following notions are well-known in approximation theory [Lor66,
Tim63].
Denitions 25 (Moduli of Continuity) The modulus of continuity of the function f()
dened on domain D is the following function of  2 [0;
The modulus of continuity of the function f(; ) is the following function of  x ;  y 2 [0;
The partial moduli of continuity of the function f(; ) are the following functions of  2
sup
sup
We now present some facts which are easily proved.
Facts 26 The following are true of the modulus of continuity.
1.
2.
3. !(f
4. If f 0 , the derivative of f exists, and is bounded in D, then
5.
7. If f(; ) is symmetric, then !(f
8. If b
x is the partial derivative of f with respect to x, then !(f
f .
We need a notion of an \inverse" of G. If G[x;
y.
Since G is symmetric, G 1
2 and we denote G 1 [z;
An Example. Wherever necessary, we will illustrate our scheme using the functional
equation
y). The solution to this functional
equation is some constant C. The following fact [Tit47] is useful in locating
the maxima of analytic functions.
Fact 27 (Maximum Modulus Principle) If f is analytic in a compact region D, then f
attains extremum only on the boundary of D.
Over a bounded rectangle is analytic and hence by Fact
27, attains maximum on the boundary. G 2 C 1 [L; U ] in D (i.e., continuously dierentiable).
We have G 0
which is a decreasing function of x. By Fact 27, kG 0
attains maximum when
Therefore, using 26,
4.2 Stability for Functional Equations
In this section, we prove (under some assumptions) that, if a function g satises a functional
equation approximately everywhere, then it is close to a function h that satises
the functional equation exactly everywhere. Our functional equations are of the form
Example. If g(x
for all valid x; y, then there is a function h such
that h(x
for all valid x; y, and and h(x)  0 g(x) for all valid x. The
domains for the valid values of x, y, as well as the relationship between  and  0 will be
discussed later.
in D n;s . In the following sections we show how to construct the function h that
is close to g, satisfying a particular functional equation. Given such an h, let e(x) denote
We consider the cases when c < 1, rst show how to obtain h, and then
obtain bounds on e(x). Then, we can conclude that h, which satises the functional equation
everywhere, also approximates g; i.e., the functional equation is stable.
Call x
s
even (resp. odd) if x is even (resp. odd).
4.2.1 When c < 1
We rst construct h by setting h( 1
s
s
This determines h for all values in D by the
fact that h satises the functional equation.
We obtain a relationship between the error at x and 2x using the functional equation.
Lemma 28 e(2x)  ce(x) +.
Proof.
using the denition of the Modulus of Continuity, jH 1
We have to explore the relationship between e(x+ 1
s
and e(x). For simplicity, let H
s
s
))j  d for some constant d. Now,
s
Proof. e(x
s
s
s
s
s
)]j. But,
We will show a scheme to bound e(x) for all x when d < 1. This scheme can be thought of
as an enumeration strategy, where at each step of the process, certain constraint equations
have to be satised. First, we will show a canonical listing of elements in D
n;s .
Construct a binary tree T k in the following manner. The nodes of the tree are labeled
with elements from D
n;s . The root of the tree is labeled 1
s . If x is the label of a node, then
2x is the label of its left child (if 2x is not already in the tree). and x
s
is the label of
its right child (if x
s
is not already in the tree). Using induction, we can prove that T k
contains all elements of D
n;s . This is by induction on k. When the tree is obvious.
Suppose the above requirement. Build T k as follows: For every leaf (with label
of T k 1 , a left child 2x is added and to that left child, a right child 2x
s
is added. By
assumption on T k 1 , T k has all nodes in D
n=2;s . Moreover, each left child generates an even
element in ( 2 k 1
s
and each right child generates an odd element in ( 2 k
s
Corollary In T k , if x is even (except root), then x is a left child; if x is odd, then x is
a right child.
A canonical way of listing elements in D
n;s arises from a preorder traversal of T k . This
ordering is used in our inductive argument.
Lemma 31 For all x
n;s , if x is even, then e(x)  1+c
Proof. We will prove this by induction on the preorder enumeration of the tree given by the
above ordering. Let x be the next element to be enumerated. By preorder listing, its parent
has already been enumerated and hence, its error is known. If is even, from Corollary
30, it is a left child, and hence generated by a 2y operation. Hence, e(y)  2
by induction
hypothesis. This together with Lemma 28 yields e(x)  ce(y)
preserving the induction hypothesis. If
s
is odd, from Corollary 30, it is a right
child, and hence generated by a y
by induction
hypothesis. This together with Lemma 29 and d  1 yields e(x)  de(y)
1+c
, preserving the induction hypothesis.
This yields (under the assumptions made before on c and d): the following theorem
Theorem 32 The addition theorem is (D
)-stable.
With our example, we have H 1
s
from which H 0
s
s
s
Thus, d  1. By Theorem 32,
we have e(x)  4 for all x
n;s . When n is not a power of 2, we can argue in the following
manner. From our proof, we see that we use very specic values of x; y in the approximate
functional equation. First we extend D
n;s to nearest power of 2 to get D 0 and dene values
of g at these new points: at even x (= 2y) let and at odd x (= y
These can be thought of new assumptions on g which are satised
\exactly" (i.e., without error ). We can use Lemma 31 to conclude that there is a linear
h on D 0 that is 2
close to g. Hence, h is close to g even on D
n;s . To argue about D n;s ,
we pick a \pivot" point in D n;s (0 for simplicity). Now, we have h(
Therefore, as before, we have e( x)
When d  1, the error can no longer be bounded. In this case, we have c  1 < d. Let
cd. We can see from the structure of T k that the maximum error can occur at 2 k 1
s
By simple induction on the depth of the tree, the error is given by e(
s
. If e < 1, we obtain a constant error bound of
by geometric summation. Otherwise, we obtain
4.2.2 When c > 1
In this case, we require additional assumptions. We dene the quantity
Note that !(f ;
some c 0 > 1.
s
s
the addition theorem, this can be used to x all of h,
1 is well-dened. Let
As before, we rst obtain a relationship between the error at x and at 2x using the
addition theorem.
Lemma
Proof. We have as in Lemma 28, jH 1 . By denition
our assumption, we get e(x)
For simplicity, let H 3
s
s
x] and let !(H 3 ; )  d for some constant d.
The following lemma can be proved easily.
Lemma 34 e(x)  de( 2 k
s
our construction. We adopt a strategy similar to the one in the previous section.
Construct a binary tree T k in the following manner. The nodes of the tree are labeled
with elements from D
n;s . The root of the tree is labeled 2 k
s
. If x is the label of a node and
x is even, then x=2 is the label of its left child (if x=2 is not already in the tree). and 2 k
s
x
is the label of its right child (if 2 k
s x is not already in the tree). It is easy to see that T k
contains all elements of D
n;s .
Corollary
s
(except the root), then x is a left child and if x
s
, then x is
a right child.
We use the preorder enumeration of D
n;s using T k in the following inductive argument.
Lemma 36 For all x
s
and d  1, then e(x)  2c 0
s
then
Proof. The proof is by induction on the preorder enumeration of the tree given by the
above ordering. It uses Lemma 34 and Corollary 35, and is similar in
avor to the proof of
Lemma 31.
This yields (under the assumptions on c and d) the following theorem:
Theorem 37 The addition theorem is (D
This case arises for linearity where H 1 2. Using the above
theorem, we get a weaker bound of e(x)  3 (as opposed to  2 by Corollary 8). Similar
techniques as in previous section can be used to argue about D n;s .
The case when d > 1 can be handled by schemes as in the previous section.
4.2.3 When
In this case, it means that !(H or in other words, by Fact 26, kH 0
1. By Fact
27, the maximum occurs only at the boundary of the domain. Hence, we can test by looking
at a subdomain in which the maximum is less than 1.
4.2.4 Jensen's Equation
Jensen's equation is the following: 8x; y 2 D n;s ; f( f(x)+f(y). The solution to this
functional equation is ane linearity i.e., constants a; b. Jensen's
equation can be proved approximately robust by modifying the proof of its robustness in
[Rub94]. We will show a modied version of our technique for proving its stability. As
before, we have 8x; y 2 D n;s ; g( x+y)  g(x)+g(y). To prove the stability of this equation,
we construct an ane linear h. Note that two points are necessary and sucient to fully
determine h. We set h( n
s ) and
Lemma 38 e( x+y)  e(x)=2
Proof. e(
The following corollary is immediate.
Corollary
Proof. Since for
We construct a slightly dierent tree T k in this case. The root of T k is labeled by n
s
and if x
is the label of a node, then x=2 (if integral and not already present) is label of its left child
and ( n
integral and not already present) is the label of its right child. It is easy
to see that T k contains all elements of D
n;s .
Theorem 40 The Jensen equation is (D
Proof. The proof is by induction on enumeration order of T k given by, say, a breadth-rst
traversal. Clearly, at the root, e( n
s
2. Now, if e(x)  2, then, consider its
children. Its left (resp. right) child (if exists) is x=2 (resp.
s
)=2). Thus, by Corollary
39, we have e( x)
4.3 Approximate Robustness for Functional Equations
As in [GLR + 91, RS92], we test the program on D 2p;s and make conclusions about D n;s .
The relationship between p and n will be determined later. The domain has to be such
that G is analytic in it. Therefore, we consider the case when f is bounded on D 2p;s , i.e.,
G be the family of functions f that satisfy the following conditions:
1. Pr
x2D 2p;s
2. Pr
x2D 2p;s
3. Pr
x;y2D2p;s
4. Pr
Note that the membership in G is easy to determine by sampling. We can dene a distribution
(n;s) such that if P satises the functional equation on E (n;s) with probability at least 1 ,
then P also satises the following four properties.
1. Pr
x;y2Dp;s
2. Pr
x;y2D p;s
3. Pr
x;y2D p;s
4. Pr
x2Dn;s ;y2Dp;s
E (n;s) is dened by
ipping a fair four-sided die and on outcome i 2 f1; 2; 3; 4g, choosing
inputs according to the distribution given in the (i)-th property above. Recall from Fact 26
that b
We can then show the following:
Theorem 41 The addition theorem with the distribution E (n;s) is
)-approximately robust.
Dene for x 2 D p;s ,
inequality, denition
of g, and the properties of P , it is easy to show the following:
Lemma 42 Pr x2Dn;s [g(x)  P (x)] > 1 2.
Proof. Consider the set of elements n;s such that Pr y2Dp;s [P (x)  G[P (x
1. If the fraction of such elements is more than 2, then it contradicts hypothesis
on P that Pr x2Dn;s ;y2D p;s [P (x)  G[P . For the rest, for
at least half of the y's, P (x)  G[P dening g to be the median (over y's
in D p;s ), we have for these elements
For simplicity of notation, let P x denote P (x) for any x 2 D p;s and G x;y denote G[P (x); P (y)]
for any x; y 2 D p;s . Since G is xed, we will drop G from the modulus of continuity. Let
Fact 43 For x 2 D 2n;s , Pr y2D p;s [x
Lemma 44 For x 2 D 2n;s , Pr
Proof. Pr
Note that x z, y, z are all random. The error in the rst step (due to computation of P x y
is !(; 0) and the equation holds with probability  1  by hypothesis (3). The bounds on
G x z;z y also hold with probability at least 1 2 by hypotheses (3), (4) and so the error is
just !(; 0). There is a loss of 2
probability for x z to be in D p;s by Fact 43. The
next line is just rewriting. In a similar manner, the nal equation holds with probability at
least 1  by hypothesis (2) and the error bound is !(0; ) The bounds on random points
hold with probability at least 1 8 by hypotheses (a), (b) on P to make
the error !(0; ). Hence, the total error is Fact 26 and the
equality holds with probability at least 1 12 2
The following lemma, which helps us to bound the error, is from [KS95].
Lemma is a random graph with edges inserted with probability
is a graph where the probability
that a randomly chosen node is not in the largest clique is at most .
Proof. Let p. The crucial observation is that the clique number of G 2 is at least as
big as the maximum degree in G. Hence, for a random node x, probability that x is present
in the largest clique in G 2 is more than the probability that x is connected to the maximum
degree vertex (say y) in G. Let the degrees of vertices in G be d 1      d p . Then, the
degree of y is d 1 . The probability that x has an edge to y is d 1 =p. Probability of an edge
between two random nodes is 1
=p. The lemma
follows.
The following shows, in some sense, that g is well-dened:
Lemma 46 For all x 2 D 2n;s , Pr y2D p;s [g(x)  2 0 G x y;y
, where
Proof. We have the following: for all x 2 D 2n;s , Pr y;z2D p;s [G x y;y  0 G x z;z
Now, we use Lemma 45. If G denotes a graph in which (y; z) is an edge i G x y;y  0 G x z;z
then G 2 denotes the graph in which (y; z) is an edge i G x y;y  2 0 G x z;z . Now, using
Lemma 45, we have that number of elements that are 2 0 away from the largest clique is at
most 2. Thus, at least 1 2 of elements are within 2 0 of each other. If  < 1=2 and since
g(x) is the median, the lemma follows.
Now, the following theorem completes the proof that g satises the addition theorem approximately

Theorem 47 For all with probability at least 1
, where
G).
Proof. Pr
u;v2D p;s
!(0;) G u;x+y u
By Lemma 46, the rst equality holds with probability 1
and error !(2
bounds on G u;x u hold with probability at least 1 4 to make the error !(2
Fact 26. The second and third equalities are
always true. The fourth equality holds with probability at least 1
by hypothesis (1)
on P and the error accrued is !(0; !(; 0)). The bounds on P
with probability at least 1 10 to make the error !(0; !(; 0). The fth
equality also holds with probability at least 1  2
by hypothesis (1) on P and the error
accrued is !(0; after bounds on P (with probability at least 1 4).
The nal equality holds with probability at least 1 12 2
by Lemma 46 and error is
Thus, the total error is 9!(!(;
G by
Fact 26. Hence, using Fact 26, !(!(; 0))   b
If  < 1=56; p > 11n, we have 1 56 9
> 0 and so the above lemma is true with
probability 1. In the case of our example function, we already calculated b
Hence,
5 Approximate Self-Testing and Self-Correcting
5.1 Denitions
The following modications of denitions from [GLR capture the idea of approximate
checking, self-testing, and self-correcting in a formal manner. Let P be a program for f ,
n;s an input to P , and  the condence parameter.
Denition 48 A )-approximate result checker for f is a probabilistic
oracle program T that, given P , x 2 D n;s , and , satises the following:
0)-approximates f on D (n;s) ) Pr[T P outputs \PASS"]  1 .
(2) outputs \FAIL"]  1 .
Denition )-approximate self-tester for f is a probabilistic oracle
program T that, given P and , satises the following:
0)-approximates f on D (n;s) ) Pr[T P outputs \PASS"]  1 .
(2) P does not ( 2 ; )-approximate f on D n;s ) Pr[T P outputs \FAIL"]  1 .
Observe that if a property is )-approximately robust and (D n;s ; D n 0 ;s
stable, it is possible to do equality testing for the function family satisfying the property,
then it is possible to construct a
Denition 50 A (; ;  0 ; D (n;s) ; D n;s )-approximate self-corrector for f is a probabilistic
oracle program SC P
f that, given P that (; )-approximates f on D (n;s) , x 2 D n;s , and ,
outputs SC P
f (x) such that Pr[SC P
Note that a
self-corrector yield a
5.2 Constructing Approximate Self-Correctors
We illustrate how to build approximate self-correctors for functional equations. The approach
in this subsection follows [BLR93, GLR
Then the self-corrector SC P
f at input x is constructed as
follows. To obtain a condence of :
1. choose random points y
2. let SC P
f (x) be the median of G[P
By the assumption on , both the calls to P are within  of f with probability greater than
3=4. In this case, the value of G[P
G away from f(x) (see Section 4.1
for b
G). Using Cherno bounds, we can see that at least half of the values G[P
are at most  0 away from f(x). Thus, their median SC P
f (x) is also at most  0 away from
f(x).
For degree d polynomials, a similar self-corrector works with  In
order to pass good programs, this is almost the best  0 possible using the evenly spaced
interpolation equation since the coecients of the interpolation equation are
e d ). Using
interpolation equations that do not use evenly spaced points seem to require  0 that is
dependent on the size of the domain.
5.3 Constructing Approximate Self-Testers
The following is a self-tester for any function satisfying an addition theorem f(x
computing the function family F over D n;s . We use the notation from Section
4.1. To obtain a condence of , we choose random points x
O(maxf1=; 48g ln 1=)) and verify the assumptions on program P in the beginning of Section
4.3. If P passes the test, then using Cherno bounds, approximate robustness, and
stability of the property, we are guaranteed that P approximates some function in F . We
next perform the equality test to ensure that P approximates the given f 2 F . Assume
that f( 1
s
s
Modifying the proofs in Section
4.2, one can show that if there is a constant  such that SC P
s
s
s
s
1), the error between SC P
f and f can be bounded by a constant
on the rest of D n;s . Since SC P
approximates P , the correctness of the self-tester follows.
For polynomials, we use random sampling to verify the conditions on program P required
for approximate robustness that are given in the beginning of Section 3.3. If P satises
the conditions then using the approximate robustness and stability of the evenly spaced
interpolation equation, P is guaranteed to approximate some degree d polynomial h. To
perform the equality test that determines if P approximates the correct polynomial f , we
assume that the tester is given the correct value of the polynomial f at evenly
spaced points x
s
. Using the self-corrector SC P
f from Section 5.2,
we have kSC P
. The equality tester now tests that for all x i ,
Call an input x bad if jf(x) h(x)j >
If x is bad then jf(x) SC P
. If x is a sample point, and x is bad, then
the test would have failed. Dene a bad interval to be a sequence of consecutive bad points.
If the test passes, then any bad interval in the domain can be of length at most (2n
because any longer interval would contain at least one sample point. The two sample points
immediately preceding and following the bad interval satisfy jf(x) h(x)j   00 . This implies
that there must be a local maximum of f h (a degree d polynomial) inside the bad interval.
Since there are only d extrema of f h, there can be at most d bad intervals, and so the total
number of bad points is at most d(2n 1)='. Thus, on 1  fraction of D n;s , SC P
f 's error is
at most  These arguments can be generalized to the k-variate case by partitioning
the k-dimensional space into ((d cubes.
5.4 Reductions Between Functional Equations
This section explores the idea of using reductions among functions (as in [BK89, ABC
to obtain approximate self-testers for new functions. Consider any pair of functions f
that are interreducible via functional equations. Suppose we have an approximate self-
tester for f 1 and let there exist continuous functions F; F 1 such that f 2
Given a program P 2 computing f 2 , construct program P 1 computing
. We can then self-test P 1 . Suppose P 1 is -close to f 1 on a large portion of the
domain. Then for every x for which P 1 (x) is -close to f 1 (x), we bound the deviation of
If we can bound the right-hand side by a constant (at least for a portion of the domain), we
can bound the maximum deviation  0 of P 2 from f 2 . This idea can be used to give simple
and alternative approximate self-testers for functions like sin x; cos x; sinh x; cosh x which can
be reduced to e x .
Suppose we are given a
we want an approximate self-tester for the function f 2 given by f 2 x. By the Euler
Given a program P 2 that supposedly computes
, we can build a program P 1 (for e ix ) out of the given P 2 (for cos x) and self-test P 1 .
Let the range of f 1 be equipped with the following
In other words, in our case, we have jP 1 (x) e ix
This metric ensures that P 1 is erroneous on x if and
only if P 2 is erroneous on at least one of x; x+3=2. Alternatively, there is no \cancellation"
of errors.
Suppose P 1 is what can we say about fraction of the
\bad" domain for P 1 , the errors can occur in both the places where P 2 is invoked. Hence, at
most fraction of the domain for P 2 is bad. The rest of the domain for P 1 is  1 -close to
which by our metric implies P 2 is also  1 -close to f 2 . Thus, P 2 is
Similarly, suppose P 1 is not not good on at least  2 fraction of the
domain, where P 1 is not  2 -close to f 1 . Thus, at these points in the domain, at least one of
points where P 2 is called is denitely not  2 =2-close to f 2 . Thus, P 2 is not
Therefore, we have an approximate self-tester for f 2 from a
approximate self-tester for f 1 , given by [GLR

Acknowledgements

. We would like to thank Janos Aczel (U. of Waterloo), Peter
Borwein (Simon Fraser U.), Gian Luigi Forti (U. of Milan), D. Sivakumar (SUNY, Bualo),
Madhu Sudan (IBM, Yorktown), and Nick Trefethen (Cornell U.), for their suggestions and
pointers.



--R

Lectures on Functional Equations and their Applications.
Functions with bounded n-th dierences
Checking approximate computations over the reals.
Proof veri
Probabilistic checking of proofs: A new characterization of NP.

Designing programs that check their work.

Software Reliability via Run-Time Result-Checking Journal of the ACM <Volume>44</Volume><Issue>(6)</Issue>:<Pages>826-849</Pages>
Re ections on the Pentium division bug.
Functional Equations and Modeling in Science and Engineering.
The stability problem for a generalized Cauchy type functional equation.
Performance evaluation of programs related to the real gamma function.
The use of Taylor series to test accuracy of function programs.
A representation theorem for
An existence and stability theorem for a class of functional equations.

Stability of homomorphisms and completeness.
Local stability of the functional equation characterizing polynomial func- tions

On the stability of the linear functional equation.

New directions in testing.
Approximation of Functions.
The Power of Interaction.
Grundlegende Eigenschaften der Polynomischen Opera- tionen
Robust functional equations and their applications to program test- ing
Testing polynomial functions e
Robust characterizations of polynomials and their applications to program testing.
Sull'approssimazione delle applicazioni localmente
Personal Communication
Theory of Approximation of Functions of a Real Variable.
The Theory of Functions.
Algebraic Methods in Hardware/Software Testing.


--TR
program testing;polynomials;property testing;approximate testing;functional equations