BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR94-1435
ENTRY:: 1994-08-26
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Robust Functional Equations with Applications to 
        Self-Testing/Correcting
AUTHOR:: Rubinfeld, Ronitt
DATE:: July 1994
PAGES:: 16
ABSTRACT:: 
The idea of self-testing/correcting programs, introduced in [BLR90], is a 
powerful tool for attacking the problem of program correctness. However, one 
of the main criticisms of this approach was that it seemed to have limited 
scope, applying only to linear and low degree polynomial functions. This 
paper provides results which show that the concept of self-testing/correcting 
has much broader applications than we previously understood. We concentrate 
on functions $f$ satisfying functional equations, in particular, those of the 
form $\forall x,y~~ F[f(x-y), f(x+y), f(x),f(y)]=0$, where $F$ is an 
algebraic function. We show that self-testers and self-correctors can be 
found for many such functions, including $\tan{x},{1 \over {1+\cot{x}}},
{Ax \over {1-Ax}},\cosh{x}$. We make an initial attempt at characterizing 
properties of functional equations that make them useful for self-testing and 
self-correcting.
END:: CORNELLCS//TR94-1435
BODY::
Robust Functional Equations with
Applications to Self-TestinglCorrecting
Ronitt Rubinfeld*
TR 94-1435
July1994
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
*Cornell University. email: ronifl?cs.comell.edu. This work is supported by ONR
Young Investigator Award NOOOl 4-93-1-0590 and United States - Israel Binational
Science Foundation Grant 92-00226.
Robust functional equations with applications to
self-testing/correcting
Ronitt Rubinfeld *
July 6,1994
Abstract
The idea of self-testing/correcting programs, introduced in [BLR9o], is a powerful tool for at-
tacking the problem of program correctness. However, one of the main criticisms of this approach
was that it seemed to have limited scope, applying only to linear and low degree polynomial
functions. This paper provides results which show that the concept of self-testing/correcting
has much broader applications than we previously understood. We concentrate on functions
f satisfying functional equations, in particular, those of the form Vr, y F[f(x --H y), f(x +
y), f(z), f(y)] = 0, where F is an algebraic function. We show that self-testers and self-correctors
can be found for many such functions, including tan:, i+c",t x' lAAXz cosh:. We make an ini-
tial attempt at characterizing properties of functional equations that make them useful for
self-testing and self-conecting.
*Cornell University. eiail: ronittCcs.cornell.edu. This work is supported by ONR Young Investigator
Award Nooo14- 93-1-0590 and United States - Israel Binational Science Foundation Grant 92-00226.
1 Introduction
In order to attack the problem of program correctness, the powerful tool of self-testing/correcting
programs was introduced ill [BLR9Oj.1 If a function has a self-correcting program, then given a
program P for computing the function that is correct on most inputs, one can transform P into
a new randomized program that is correct on each input with high probability and is no more
complicated than P. Self-testing programs allow one to ascertain that P is correct on a large
enough fraction of the inputs so that it is capable of being self-corrected. Problems that can be
viewed as linear and low degree polynomial functions, such as matrix multiplication, integer division,
sine/cosine (over domalns consisting of nth roots of unity) and determinant, have been shown to
have self-testers and self-correctors [BLR9oj [BF9O] [Li9l] [CL9oj [GLRSW9lj [RS92J[RS93] [AHKJ.
Mthough many functions can be viewed as linear functions or low degree polynomials, one concern
was that these might be the only examples of functions that have self-testers and self-correctors.
This paper provides results which show that the concept of self-testing/correcting has much broader
applications than we previously understood. We show that self-testers and self-correctors can be
found for many other numerical functions, including several of the trigonometric functions.
We do this by bringing the classical theory of functional equations to bear on the area of self-
testing/correcting. The theory of functional equations is a mathematical area concerned with
determining classes of functions satisfying given sets of properties. The prototypical question in
the area of functional equations takes the following form: Given a set of properties (functional
equations) over a specified domain, determine the family of functions that satisfy them. In this
paper we study functional equations F = 0, where F contains k independent variables, and an
unknown function f as well as a finite number of known functions (cf. [A66]). The linearity property
Vx, y f(z + y) --H f(x) --H f(y) = 0 is one of the famous, well-studied functional equations referred
to as Cauchy's equations. We provide techniques aimed at identifying conditions on functional
equations that make them useful for self-testing/correcting.
Self-correcting. It is shown in [BLR9O] that self-correctors exist for any function that is ran-
dom self-reducible2, since if the program is known to be correct on most inputs, then the correct
value of the function at any particular input x can be inferred, even though the program may
be incorrect on input x. In particular, any function satisfying the linearity property is random
self-reducible[BLR9Oj. Here we show that efficient self-correctors exist for functions satisfying any
one of a class of functional equations, namely those of the general form Vx, y F[f(x --H y), f(x +
y), f(:), f(y)] = 0, where F is an algebralc function that has the property that given three of
f(x --H y), f(x + y), f(x), f(y), F can be used to efficiently solve for the remaining one (see examples
in Figures 1,2).
Self-testing. For a function f that satisfies a given property, we concentrate on self-testers which
operate by testing that the program satisfies the property for randomly chosen inputs. We are
particularly interested in properties that are more efficient to test than computing the function
f. In order to show that such tests work, the main technique used has been to show that these
properties are robust (formal definitions are given in [RS93]):
Definition 1 (informal) Let ? be the family of functions satisfying property F = 0. F = 0 is
1A notion similar to self-correcting is independently proposed in [Li9l].
2f is random sell-reducible if f can be computed at any particular input z by an easily computable function
f(r) = G[f(yi)f(yk)] where G can be computed more efficiently than f and the ?j'S are uniformly distributed,
though not necessarily independent.
an (E, 6)-robust property over domain D if for any program that satisfies F = 0 with probability
> 1 --H 6 when inputs are randomly chosen from D, there exists a function f E ? which agrees with
the program on at least 1 --H E fraction of the inputs in D.
For example, the function f(x) = x mod R is uniquely specified by the properties that (1) f is linear,
i.e., Vx, y f(x) + f(? =--H f(x + y) mod R, (2) f has slope 1, i.e., Vx f(x) + 1 ::::--H f(x + 1) mod R.
In [13LR90], the property of being a linear function is shown to be robust, i.e., if (1) is satisfied for
most x, y, then there is some function g(x) = cx mod R such that f(x) = g(x) for most x. If in
addition (2) is satisfied for most x then f(x) = x mod R for most x. Thus, it is only necessary to
check that the program satisfies the given properties at a relatively small number (in this case, a
constant independent of Ixi, RI) of randomly selected inputs in order to guarantee that the program
usually computes the correct values. The function f(x) = x mod ft is also uniquely specified by the
following properties which are not robust: (1) Vx f(x) + f(l) = f(x + 1) mod R, and (2) f(O) = 0.
The function that is 0 at x = 0, x + 1 for 0 < x < R/2, and x + 10 for all other x is almost never
equivalent to f. Yet this function satisfies (1) at almost all x and always satisfies (2).
We initiate a systematic study aimed at determining which functional equations are robust. Our
results have significance to the area of functional equations, allowing us to determine when a
property can be phrased in terms of the words "for most" rather than the words "for all". The
robustness of linearity has played a key role in recent results in complexity theory[ALMSS92].
We begin by investigating conditions on functional equations of the form Vx, y F[f(x --H y), f(x +
y), f(x), f(y)] = 0 that imply robustness. We show that if the equation can be written as Vx, y f(x+
= G[f(x), f(y)j (a generalization of Cauchy's functional equation that is referred to as an
addition theorem), then it is robust. This work applies to several trigonometric functions such as
tan x, 1+c1otx' lAAXx ,cosh x, as well as including previous results in [BLR90] on linearity testing as
a special case. Examples of functions satisfying addition theorems from [A66][AD89] [CR92] are
given in Figure 1. We then show that having efficient self-testers is not limited to such equations,
by giving techniques that apply to several other functional equations (the first three examples in
Figure 2), including d'AIembert's equation Vx, y f(x + y) + f(x --H y) = 2f(x)f(y).
Finally, we make an initial step in the direction of characterizing properties of functional equations
that make them robust. We isolate a combinatorial property of functional equations that is essential
for robustness. We consider the class of functional equations that only relate function values at
inputs x to function values at inputs that are linear functions of x. We use the absence of the
combinatorial property in such functional equations to show that they are not robust. We show
conditions under which functional equations relating the function value at each input x to function
values at each subset of k other inputs are robust.
Functional equations have been used in the study of various functions that arise in many areas within
mathematics, physics and economics. The techniques used to derive our results seem amenable to
further generalization, and may apply to an even wider variety of numerical functions.
Organization of paper In the next section we give informal definitions of the concepts used in
the paper. In Section 3 we present the self-testers and self-correctors based on the general form of
the functional equation Vx, y F[f(x --H y), f(x + y), f(x), f(y)] = 0, and prove that they are correct,
assuming the robustness of the property defined by the functional equation. In Section 4 we present
technical theorems, showing the robustness of the addition theorems and of d'Alembert's equation.
In Section 5 we investigate properties of functional equations that make them useful for self-testing
and self-correcting. In Section 6 we discuss our conclusions and directions for further research.
2
Equation			Solution			1
f(x + y) = #7A+x?i?			f(x) = tanAx
f(x+y)=L\%(%jXx+1Ii?1			f(x)=cotAx
AX+Y)=?ff?x+I?A			f(z)=AtanhBr
Az)=Ck
f(x + y) = f(x)tf(2Yi)?????7(?)			f(x) =			1
1+cotAx
f(x + `s) = 21(x)+12(!X()y+)1(2YFxl)1(?)?l			f(x) =			1
1+tanAx
f(x + v) =			f(x) =
f(z + y) = !(X)+1!)??--H2f(x)J(1')			f(x) = F?AAZx
--H j?xj+j'(?)--H2f(z)f(s,jcosa			f(x) = sin Ax
x t y --H			1--Hf(x)I(?)			sin Ax+a
x + = J?x)+Jt?)--H2Jx)!S,)cosna			= srnh Ax
v			l--Hf(xf(y			sinh Ax+a
f(x + ?) = J(x)+!(?f+??!x?)(i7?i) cosha f(x) = srnS???hxA+?a
f(x+y) = f(x)f(y) --H ThfThx)2ftZTh(y)2 f(x) = cos(Ax)
f(x + v) = f(x)f(y) + mm2?1?2?1 f(x) = cosli (Ax)
Figure 1: Examples of fuuctious satisfying addition theorems
3
Equation			Solution
f(x+y)+1(x--Hy)=21(x)			f(x)=Ax+a
1(x+y)+1(x --H y) = 21(x)f(y)			1(x)			= 0,cosAx,coshAx
f(x+y)+1(x--Hy)=2[1(x)+1(y)]			1(x) =Ax2
f(x+y)--H1(x--Hy)=21(y)			1(x)=Ax
1(x+y)f(x ?y) = 1(x)2			1(x) = a
Ax+y)--H1(x--Hy) =4WmxV(y)			1(x) Ax2
f(x+y)1(x --H y) = 1(x)2 --H 1(y)2			1(x) = Ax, ksinAx ,ksinhAx
Figure 2: Examples of functions satisfying F[f(x --H y),f(x +
y),f(x),f(y)] = 0
2 Background
Seff-testing/correcting programs. We give informal definitions of self-testers and self-correctors.
Formal definitions are given in [BLR9O]. Let Prx?x[?] denote the probability of when x is uni-
formly chosen from X. We say that program P e-computes f on D if Prz?D[P(x) = f(x)] > 1 --H
An (e1, e2)-setI-tester (0 < e1 < e2) for f on D must fall any program that does not e2-compute f
on D, and must pass any program that e1-computes f on D (note that the behavior of the tester
is not specified for all programs). The tester should satisfy these conditions with error probability
at most P, where ? is a confidence parameter input by the user. For simplicity, we assume that
E1 = 0, and we drop that parameter from our claims. An ?-se(f-correctorfor f on D is an algorithm
C that uses P as a black box, such that for every x E D and P, Pr[C?(x) = f(x)] > 1 --H p, for
every P which &computes f on D. Furthermore, all require only a small multiplicative overhead
over the running time of P and are different, simpler and faster than any correct program for f in
a precise sense defined in [BK89].
Robust properties are used for self-testing and self-correcting functions that can be viewed as linear
and low degree polynomial functions, including integer multiplication, the mod function, modu-
lar multiplication, integer division, polynomial multiplication, modular exponentiation, sine/cosine
functions over domains consisting of nth roots of unity, low degree polynomial functions and deter-
minant [BLR9O] [AHKj [CL9o] [BF9OJ (Li9l] [GLRSW91J [RS92j [RS93] [AS92J[ALMSS92] [BFL9I]
[FGLSS9l]. Self-testers can also be constructed by first finding a checker [BK89] for the function,
whereas checkers can be constructed by finding both a self-tester and a self-corrector for the function
[BLR90j.
Functional equations. Many of the functions used in physics, economics and mathematics are
defined by the properties that they must satisfy. The mathematical field of functional equations is
concerned with the following prototypical problem: Given a set of properties (functional equations)
over a particular domain, completely characterize the set of functions that satisfy them.
4
Informally, a functional equation is an equation F = 0, where F contains k independent variables,
and n> 1 unknown functions h1,h2,..., hn as well as afinite number of known functions (cf. [A66]).
A system of functional equations can also be defined. A particular solution of a functional equation
is a system of functions that satisfies the equation in the given domain. The general solution, ?,
is the family of solutions that satisfy the equation in the given domain. In this paper, we will be
concerned with domains that are finite subsets of the rationals, since this natural class of domains
can be internally represented in a computer. We are also interested in domains that are finite
fields, because it is much simpler to reason about such fields, and then to use known techniques for
converting results about finite field domains to results about rational domains [GLRSW9l][RS92j.
General classes of functional equations have been identified. Algebraic addition theorems are those
of the form
Vx, y F[f(x + ?), Ax), 1(Y)] = 0
where F is any algebraic function. Algebraic addition theorems are of importance because of their
use as a starting point in the development of the theory of elliptic curves by Weierstrass. The
fundions that have algebraic addition theorems are exactly those which are algebraic functions,
algebraic functions of a periodic function and algebraic functions of a doubly periodic function (a
rational function of Weierstrass' ?function and its derivative) [F65].
Addition theorems, of the form Vx, y f(x + y) = G[f(x), f(y)J, are a special case of algebraic
addition theorems in which F can be solved for f(x + y). The functions that satisfy the addition
theorems are those that can be expressed as a group operation. If G is a polynomial, then the
functions which satisfy it are linear functions and linear functions of exponential functions. If G is
an algebraic function, then the functions which satisfy G are rational functions of x, e? or doubly
periodic functions (cf. [A66] p.6l).
Other examples offunctional equations include those of the form Vx, y F[f(x--Hy), f(x+y), f(x), 1(y), x, =
0, and generalizations such as f(9(x + ?)) = C(f(x --H ?), f(x), f(y), x, y) for some algebraic function
g. d'Alembert's equation f(x + y) + f(x --H y) = 2f(z)f(y) is a an example of such an equation
(see Figures 1,2). Subtraction theorems, Vx, y f(x --H y) = G[f(x), f(y)J, are another special case
of such an equation, however it has been shown that a function that has a subtraction theorem
also has an addition theorem [A66]. There are many other types of functional equations, including
difference equations and multivariate functional equations.
3 Self-testing/correcting from robust functional equations
In this section, we give self-correctors and self-testers that are based on the class of functional
equations of the form F[f(z --H y), f(x + y), 1(x), f(y)] = 0. We refer to the function computed by
the program as P, and the correct function as f : D V'. For purposes of exposition, we assume
that V is a finite field Zp, for prime p. All results are extended to rational domains of the form
Vp,a = t?s?IIiI < pJ using known techniques from [GLRSW9lj[RS92](see appendix). We assume that
V' is a (possibly infinite) abelian group.
3.1 Self-correctors
The following self-corrector works for any function satisfying Vx, y f(x) = G[f(x--Hy), f(x+y), f(y)].
This includes functions satisfying an addition theorem of the form f(x + y) = F[f(x), 1(y)], since
5
letting z = x + y, f(z) = F[f(z --H ?), f(?)]. Self-correctors for functions that are not solvable for
f(x), but are solvable for another of f(x --H y), f(x + y), f(?) can be similarly constructed.
Program Self-Oorrect(x, p)
NHO(ln(1/P))
Do for m --H 1 N
Pick ? ER Zp
answer,n G[P(x --H y), P(z + y), P(?)j
Output the most common answer in fanswerrn : m = 1,..., NJ
Theorem 2 If P 1/12-computes f on Zp, then Vz, Pr[Self --H Correct(x, p) = f(x)] > 1 --H
The proof of this theorem follows the format of Coppersmith's version of the linearity test in
[BLR9O] and is based on the fact that since calls to P are made on uniformly distributed inputs in
Zp, at each iteration, all calls are answered correctly by P with probability at least 3/4.
3.2 Self-testers
In this section we show self-testers based on functional equations of the form F[f(x --H ?), f(z +
?), f(z), f(y)J = 0 that are robust. All tests in our examples can be made using only a constant
number of additions and multiplications. Furthermore, only a constant number of tests need to
be performed. It often happens that more than one functional equation can be used to specify a
function family; we leave it to the user to determine which of the robust functional equations are
easier to use for testing.
A family of functions may satisfy the property, and then further testing must be done to determine
that the program is computing the correct function within the family. We call this second task
equality testing. Though equality testing is often easier than the original testing task, it may stffl
be inefficient, as in the case of multivariate polynomials [RS93]. For the functions considered in this
paper, the problem of equality testing can be solved efficiently. It is often the case that there are
certain points at which the function is much easier to compute. We assume that the function values
are given at a constant number of points, such that these values in conjuction with the property
F are enough to completely specify the function. For example, for functions satisfying addition
theorems, the function values at 0 and 1 suffice to completely specify the function at all positive
integers.
We concentrate on functions that can be tested by testers of the form given below. In the following,
? is a parameter that is determined by Theorem 4.
Program Self?Test((x0,y0),(xi,yi),..., (xc, yc), P)
N			O(max?-61,24Jln(2/P))
Doform=1,...,N			?PropertyTestJ
Pick n,v ER Zp
if F[P(i --H v), P(u + v), P(n), P(v)] # 0 output FAIL and halt
Do for i = .... ., O(ln(c/P)) ? Equality Test J
6
Pick `LER Zp
If F[P(xi --H u), P(xj + u),yi, P(u)j $ 0 output FAIL and halt
Output PASS
Theorem 3 IfF is (26,6)-robust, and if P does not (1/12)-compute f on Zp, then Pr(Self --H Test(r, P) =
FAILj> 1--H p. If P f, then Se(f- Test outputs PASS. Thus, Self- Test is an --H% -self-testing program
for f on Zp.
The proof of the theorem is based 011 the robustness of F, which tells us that if there is 110 function
9 such that (1) 9 is usually equal to P and (2) 9 satisfies the property everywhere, then P is
reasonably likely to fall the test. Furthermore, if there is such a function 9, the equallty tests are
likely to fail unless 9(x0)=f(x0),... , g(xc) = f(xc) which ensures that 9 = f. Thus P fails unless
it is usually equal to f.
4 Robustness theorems
We show conditions under which the general functional equation F[f(x--Hy), f(x+y), f(x), f(y)j = 0
is robust.
4.1 Addition theorems
We show that any addition property Vx, y f(x + y) = G[f(x), f(y)] is (26,6)-robust for 6 < 1/8.
Therefore testing that P(x + y) = G[P(x), P(y)J holds at a 1 --H of the (x,y) pairs is enough to
verify that P 1/12-computes a function which has the addition property for all x, y.
Theorem 4 IfPrz,???2p[P(Z+Y) = G[P(x),P(y)]] > 1--H6, for6 < 81, then there exists a function
9 such that (1) Prx??zp[P(X) = ?(x)]> 1 --H 26 and (2)Vx,y g(x + y) =
Proof: Given any function f satisfying Vx, y f(x + y) = G[f(x), f(y)], since Zp is associative
we have that f(x + y + z) = G[f(x), f(y + z)] = G(f(x + y), f(z)], and so G[f(x), G[f(y), f(z)JJ =
G[G[f(x), f(y)], f(z)j. We show that C[P(x), G[P(y), P(z)]] = C[G[P(x), P(y)j, P(z)J for any ar-
bitrary function P. To show that C[a, G[b, c]] = G[G[a, bj, c] Va, b, c, we verify that the algebraic
function H(a,b,c) = G[a,G[b,c]] --H G[G(a,b],c] is identically 0. Let N be the total degree of
the norm of H (the maximum of the degree of the constant term and the degree of the leading
term in the minimal polynomial corresponding to the algebraic function H over Z?(a, 6, c)). It is
known that IN is polynomial in the size and degree of H. Suppose that there exists a solution
f of f(x + y) = G[f(x), f(y)j that takes on at least N3 distinct values V = ....... , VN3l. Since
Va,b,c E V, H(a,b,c) = 0, we know that H(a,b,c) =--H 0 [Z93].
The rest of the proof follows the format used in [BLR90j[RS93], and generalizes the result in
(BLR9OJ.
Define g(x) to be majz?zpfC(P(? --H z), P(z))?, where maj of a set is the function that picks the
element occuring most often (choosing arbitrarily in the case of ties). We first show that 9 is
26-close to P:
7
Lemma 5 g and P agree on more than 1 --H 26 fraction of the inputs from Zp.
Proof: Consider the set of elements x such that Pr?[P(x) = G[P(x --H z), P(z)]] < 1/2. If the
fraction of such elements is more than 26 then it contradicts the condition that Pr:,i,[P(x + ?) =
G[P(x), P(y)]]> 1 --H 6. For all remaining elements, P(x) = g(x). 0
Next we show a sense in which g is well-defined:
Lemma 6 For all x, Prz[g(x) = G[P(x --H z), P(z)]] > 1 --H 26.
Proof: ?
Pr?,? [G[P(x --H ?), P(y)] =
G[G[P(x --H y --H z), P(z)], P(y)]
G[P(x --H y --H z), G[P(z), P(y)]]
G[P(x --H (ij + z)), P(? + z)]]
> 1 --H 26
The first and third equality hold with probability 1 --H 6 by our assumption on P and since x --H
?, ?, z, x --H --H z, z + ? are all uniformly distributed in Zp. The second equality always holds since
G[a,G[b,c]] = C[G[a,b],c] Va,b,c.
The lemma now follows from the well known fact that the probability that the same object is drawn
twice from a set in two independent trials lower bounds the probability of drawing the most likely
object in one trial. ? 0
Finally, we prove that g satisfies the addition theorem everywhere:
Lemma 7 For all x,?, g(x + y) = G[9(x),9(y)].
Proof:
Pr?,? [G[g(x),g(y)] =
G[G[P(v), P(x --H v)], G[P(v), P(y --H v)]]
G[P(v), G[P(x --H v), G[P(v), P(? --H v)]]]
G[P(v), G[G[P(x --H v), P(v)], P(y --H v)]]
G[P(v), G[F(x --H v + v), P(y --H v)]]
G[P(v),P(z+ ?- v)]
g(x+y)]
> 1 --H 86> 0
By Lemma 6, the first equality holds with probability 1 --H 46 and the last equality holds with
probability 1--H26. By the assumption on P, the fourth and fifth equalities each hold with probability
1--H6. The other equalities always hold, since G[a, C[b, c]] = G[C[a, b], c] Va, b, c. Since the statement
is independent of v, v and holds with positive probability, it must hold with probability 1. 0
0 (Theorem 4)
3For conciseness, we use a somewhat nonstandard notation: for random variables a, b, c, we often reason about
the probabffity that a = c by using an intermediate variable b. We use the fact that Pr[a = c] > Pr[a = b =
1--HPr[a#b]--HPr[b#c].
4Suppose the objects are ordered so that p,' is the probability of drawing object i, and Pi > P2 > ..., then the
probability of drawing the same object twice is ?? P2 <? PiPi = pi.
8
4.2 d'Alembert's equation and others
In this section, we show that d'Membert's equation Vz, ? f(x + ?) + f(x --H ij) = 2f(x)f(y) is
a robust property. The techniques in this section can also be used to show that the equations
Vx,y f(x + y) + f(z --H y) = 2[f(z) + A?)] and Vx,? f(x + ? + f(x --H y) = 2f(x) are robust.
Except for the 0 function, all of the functions that satisfy the d'AIembert equation (or any of the
other above equations) take on the value 0 at fewer ? fraction of the domain. We make the
added assumption that the program has been tested to ensure that the program outputs 0 at on
at most ? fraction of the inputs.
The proofs in this section are similar in flavor to the proofs of the robustuess of the addition
theorems, but since the functional equation is defined on inputs that are related in different ways,
we have to take advantage of different aspects of the structure of their relationship in order to get
the desired results.
Theorem 8 IfPr?,?[P(x+y)+P(x--Hy) = 2P(x)P(y)j > 1--H6 > and Pr?[P(x) = 0] <C < 1
20'
then the function g(x) ?aj?EZp, P(?)#ofP(X+Y?P+(Pl,)(X??) ? satisfies (1) Pr?[P(x) = g(x)J > 1 --H 46
and (2)Vx,? g(x+?) +g(x --H ij) = 2g(x)g(?.
Using techniques identical to those in Lemma 5, we have:
Lemma 9 9 and P agree on more than 1 --H 46 fraction of the inputs from Zp.
Lemma 10 For all x, Pr,,[g(x) = > 1 --H 6' where 6' = 46 + 2?
Proof:
Pr?,z[ P(?) $ 0 and P(z) $ 0 and
2P(z)(P(x + y) + P(x --H y)) =
(P(x + ? + z) + P(x + y --H z)) + (P(x --H --H z) + P(x --H y + z))
(P(x + y + z) + P(z --H ? + z)) + (P(x --H --H z) + P(x + y --H
2P(y)(P(x + z) + P(x --H z))] > 1 --H 46 --H 24
P(y) = 0 or P(z) = 0 with probability at most 24. The first and third equality each hold with
probability 1--H26 by our assumption on P and since all the references to P are uniformly distributed
in Zp. The second equallty always holds. If P(y), P(z) are both nouzero and all equalities hold, then
= P(x+z)+P(x-z) The lemma now follows from the fact that the probability that
2P(z)
the same object is drawn twice from a set in two independent trials lower bounds the probability
of drawing the most likely object in one trial. 0
Finally, we can prove that 9 satisfies d'Alembert's equation everywhere:
Lemma 11 For aUz,?, 2g(x)g(?)= g(x+ y)+g(x --H
Proof:
Pr? [P(z) $ 0 and P(z) . (g(x + y) + g(x --H ?)) =
--H 2g(x). g(?)2 P(z)]
> 1 --H 56' --H 4>
P(z) = 0 with probability at most 4. By Lemma 10, the first, second and fourth equalities hold
with probability 1 --H 26', 1 --H 26' and 1 --H 6' respectively. The third equality holds with probability
1. If P(z) $ 0 and all equalities hold then 2g(:)g(y) = g(z + y) + g(x --H y). Since the statement is
independent of z and holds with positive probability, it must hold with probability 1. 0
9
5 Characterizing Robust Functional Equations
We turn to the general question of how to distinguish properties that are robust from those that
are not. We study these questions ill order to arrive at a better understanding of what makes
a functional equation robust. We isolate a key combinatorial property of functional equations
and show that having this property is a necessary condition for robustness. We then look at two
extreme types of functional equations: minimal equations, relating the function at each input x only
to function values at only one set of k other inputs, and k-total equations, relating the function at
each input x to function values at all subsets of k other inputs. We use the combinatorial property
to show conditions under which minimal equations are not robust, while leaving open the possibility
that robust minimal equations exist. We show conditions under which k-total equations are always
robust.
Definition 12 An a-separated function family ? over domain V is one for which ? > 2 and
Vfj,fj E Y, Prz?v[fi(x) = f1(x)] < a.
All of the functional equations mentioned in Figures 1,2 define a-separated function families for
a=2/IDI.
A Combinatorial Property of Robustness. Given functional equation Vx E V, y E T)k
F[f(x), f(?(x,y)),..., f(a?(x, y))] = 0, for (7j : V x Dk V, we define the undirected multigraph
CF = (V, E) where the vertices correspond to elements of V and the edges are E = ?(x, a?(x, y))?x E
V, y E Vk, 1 < j < kJ (there may be more than one edge between u and v if there is more than
one i, y such that oj(u, y) = v). For example, the graph of Vx, f(x) + 1 = f(: + 1) corresponds to
a path, and the graph of Vx, y, f(x) + f(y) = f(x + y) corresponds to a complete graph.
The following theorem shows that it is essential that CF have high connectivity in order for F to
be robust.
Theorem 13 Let ? be an a-separated function family satisfying the equation Vx E V, y E Vk,
= 0. If CF has a set of edges E' such that (1) E'l < --H51E1 and
(2) removing E' separates the vertices of CF into two components, each of size > (E + a)IVI, then
F is not (E, 6)-robust.
Proof: Suppose E' separates CF into sets A, B. Consider the function h which labels vertices in
A according to fi and vertices in B according to f2, for some fi, f2 E Y. Since ? is a-separated,
we have that Vfj E Y, PTxEv[fi(X) $ h(x)] > E. However, only tests using edges that cross the cut
wili fail. Since x, y is chosen uniformly, the edges are also chosen uniformly. Thus tests will fail
with probability <6. 0
We have shown a characterization of functional equations that is necessary for robustness. However,
we do not know if this characterization is sufficient for robustness, i.e., is it the case that if CF has
high connectivity, then F is necessarily robust? In particular, a positive answer to this question
would imply that all equations of the form Vx, y F[f(x --H y), f(x + y), f(x), f(y)j = 0 are robust.
10
Minimal functional equations. All interesting property of minimal functional equations is that
they do not seem to be useful for self-correction. Currently we have no example of a functional
equation that is robust but not useful for self-correction. Determining whether or not there exist
robust minimal functional equations could lead to a resolution 011 the relationship between self-
correction and robustness.
It is easy to see that for any minimal equation F of the form F[f(x), f(a(x))] = 0, GF can be
separated into two large pieces by removing very few edges, and thus (by Theorem 13) wffl not be
robust. It was shown in [Kl84] that any graph whose edges are defined by linear functions has a
small cut separating two large portions of the graph. The following corollary applies to functional
equations relating points x to points that are linear functions of x:
Corollary 14 Let ..... , ak be any family of linear functions with rational coefficients, and let ?
be an a-separatedfunction family satisfying the equation F[f(x),f(?(x)),f(a2(x)),..., f(a?(x))] =
0. Then F is not (1/4, 6)-robust for any constant 6.
Due to the existence of constant degree expanding graphs, we cannot use Theorem 13 to show that
all minimal functional equations are not robust.
Total functional equations. On the other end of the spectrum, we consider a class of equations
where there are no restrictions on the way inputs are related, and show that they are "always"
robust.
Let F[f(x), f(yi),... , f(yk), x, y?...., yk] = 0, thatcanbesolvedforf(x), namelyf(x) =G[f(yi),..., f(Yk), x, yi,
(because of the totallty of the equation, F and G depend on x,y1,... , y? as well as the function val-
ues at those points). Let V' be such that Vf E ?, f : V V'. We say that the solution ? to equa-
tion F is k-completeifV((yi, wi),. . ., (yk, wk)) E (V,V?)k, Anexampleofak?completefunctionfamilyisthefa?
Theorem 15 Suppose the k-totalfunctional equation F[f(x),f(y1),...,f(y?),x,yi,..., y?]
G[f(y1),. . .,f(yk),x,yi,. ..,y?] = 0 Vx,y1,. . .,y? has a complete solution ?. Then F is (6,6)-
robust V6.
Proof: Suppose P satisfies Prz,u-[P(x) = G[P(yi),. . .,P(y?),x,yi,. . .,y?]J = 1 --H 6. Then
there exists ..... ., Zk, a particular setting of the y?'s, such that the test works for > 1 --H 6 of the
x's. Let g(x) be the function in ? determined by the values of the program at z1,. . . , Zk. Then
Pr?[g(x) = P(x)] > 1 --H 6. Thus Vr,y1, .?. . , y? g(x)--HG[g(yi),... ,g(y?),x,yi,..., yk] = 0. 0
Total functional equations are as difficult to compute as the function itself and thus useless
for testing. However, given ? = ....... , a?), such that a? : V x Dk V, suppose func-
tional equations F[f(x),f(yi),. . .,f(y?),z,yi,...,y?] = OandF[f(x),f(a1(x,z)),.. .,f(a?(x,z)),x,
a1(x,z),..., a?(x, z?)j = OhavethesamecompletesolutionF.Duetothestructureofthea's, it might be
the case that F is easier to compute on those tuples defined by the a's (for example, efficient
polynomial degree tests have been constructed by only performing tests on points that are eveuly
spaced: a?(x, z) = x + iz [RS93]). If F is also robust over random choices of x, z, then a more
efficient tester can be constructed.
Let the distribution V? be the distribution defined by picking x E V, z E Vk randomiy, and
outputting (x,a1(x,z?),... , a?(x, z)). Let U be the distribution defined by picking x,yi,... , yk E V
11
and outputting (x, ...... , ?). If the a's look "random enough", we have the following theorem
showing a sense in which F is robust over random choices of x, z. This theorem implies that it is
enough to test points related by the a's. To our knowledge, this is the first time that a bound on
the runtime of the program being tested has been used to devise a tester.
Theorem 16 Let E1 denote the functional equation F[f(x),f(yi),... ,f(yk),z,yl,... ,?] = 0
Vx E V, ? E Vk, and E2 denote the functional equation F[f(x), f(ai(x, z)),... , f(a?(x, z)), x,
a1(x,z),..., ak(x, z)] = OAssnmethat(1)Ei and E2 have the same complete solution ?, (2) no
circuit of size < nk can distinguish inputs from V? and U with more than 6 advantage. and
that (3)E1 is is (E, 26)-robust. Then E2 can be used to test all programs running in time n?: if
Pr:,?[F[P(z), P(a1(x,z)),..., P(a?(x,z)),z,ai(x,z),... , a?(x, z)] = 0] > 1 --H 6, and P runs tn
<nk steps, then there is a f E Y such that Pr?[P(x) = f(x)] > 1 --H
Proof: Suppose that there exists some program P running in time n? which is wrong at > E
inputs in V but passes the tester with probability > 1 --H 6. We use it to construct a program A of
size < nk that can distinguish between inputs from V and U with more than 6 advantage. A receives
Zk, and tests whether F[P(:),P(z1)),..., P(zk),x,zl,... , zk] = 0. A outputs 1 if P passes
the test and 0 if P fails. By Theorem 15, Pr?,,,1?Eu[F[P(z),P(Y1),. . .,P(yk),x,yl,. . .,Yk] $
0] > 26, and by the assumption, Pr?,,,1??v[F[P(:),P(yi),...,P(yk),x,yi,... , ?] $ 0] <6. 0
6 Conclusions and directions for further research
We have studied the question of when functions characterized by functional equations of the form
Vx, ? F[f(x --H ?), f(x + ?), f(z), f(y)] = 0 have self-testers and self-correctors. However, we still
do not have a complete answer to this question. More generally, many other general types of
functional equations have been identified, including those on multivariate functions and systems of
functional equations, but we do not know which ones lead to self-testers and self-correctors. Given
a functional equation, is there an (efficient) algorithm to determine whether or not it is robust? Is
it the case that any property that leads to a self-corrector is robust?
An important next step is to find methods to extend all robustness results to the case of real
valued computation as in [GLRSW91] and [ABCG93]. One point of difficulty is that in real valued
computation, none of the functional equations will be satisfied exactly, even when the program is
giving very good approximations to the correct answers. Thus, the area of functional inequalities,
which is the investigation of which families of functions satisfy inequalities such as If(x + y) --H f(z) --H
< e, directly applies to this setting. The functional inequality If(x + y) --H f(x) --H f(?)I < E has
been shown to be robust in [GLRSW91], but to our knowledge is the only result in this direction.
Acknowledgements We wish to thank Mike Luby for initial conversations that eventually led
to the idea behind this work, and Nati Linial for directing us to the area of functional equations
as well as to many of the references. We thank Rich Zippel for his technical advice on the zero
testing of algebraic functions, and for guiding us through the literature regarding the scope of the
theorems in this paper. We thank Ran Canetti, Diane Hernek, Sandy Irani and Mike Luby for
greatly improving the presentation of this paper.
12
References
[ARK] Adleman, L., Huaug, M., and Kompella, K., Efficient checkers for number-theoretic
computations. Submitted to Information and Computation.
[A66] Aczel, J., Lectures on Functional Equations and their Applications, Academic Press,
1966.
[AD89J Aczel, J., Dhombres, J., Functional Equations in Several Variables, Cambridge Uni-
versity Press, 1989.
[ABCG93]
Ar, 5., M. Blum, B. Codenotti, P. Gemmell. Checking approximate computations over
the reals. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing,
pages 786-795, 1993.
[ALMSS92] 5. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the
intractability of approximation problems. In Proceedings of the 33rd IEEE Symposium
on Foundations of Computer Science, pages 14--H23, 1992.
[AS92]
[BF9O]
5. Arora and 5. Safra. Probabilistic checking of proofs: A new characterization of NP.
In Proceedings of the 33rd Annual IEEE Symposium of the Foundations of Computer
Science, pages 2--H13,1992.
D. Beaver and J. Feigenbaum. Hiding instances ill multioracle queries. In Proceedings
of the 7th Annual Symposium on Theoretical Aspects of Computer Science, Springer
Verlag LNCS 415, pages 37--H 48, 1990.
[BFL91] L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover
interactive protocols. Computational Complexity, 1:3--H40, 1991.
[BK89]
[BLR9O]
[B188]
[CR92]
[CL9O]
M. Blum and 5. Kannan. Program correctuess checking ... and the design of programs
that check their work. In Proceedings of the 21st Annual ACM Symposium on Theory
of Computing, pages 86--H97, 1989.
M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to
numerical problems. In Proceedings of the 22nd Annual ACM Symposium on Theory
of Computing, pages 73--H83, 1990.
M. Blum. Designing programs to check their work. Technical Report TR--H88--H009,
International Computer Science Institute, 1988.
Castiilo, E., Rniz-Cobo, M.R., Functional Equations and Modelling in Science and
Engineering, Marcel Dekker, Inc., 1992.
Cleve, R., Luby, M., "A Note on Self-Testing/Correcting Methods for Trigonometric
Functions", International Computer Science Institute Technical Report TR-90-032,
July, 1990.
U. Feige, 5. Goidwasser, L. Lovasz, 5. Safra, and M. Szegedy. Approximating clique is
almost NP-complete. In Proceedings of the 32nd IEEE Symposium on Foundations of
Computer Science, pages 2--H12, 1991.
13
[FGLSS9lj
[F651 A.R. Forsyth, Theory of Functions of a Complex Variable, Dover Publications, Inc.,
New York, 1965 (First published ill 1900).
[GLRSW91] P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson. Self-
testing/correcting for polynomials and for approximate functions. In Proceedings of
the 23rd Annual ACM Symposium on Theory of Computing, pages 32--H42, 1991.
[K184]
[Li91J
[RS92]
[RS93J
[Z93]
M. Kiawe. Limitations on Explicit Constructions of Expanding Graphs. in SlAM J.
Computing, Vol. 13, No. 1,pp. 156-166,February 1984.
R. Lipton. New directions in testing. Distributed Computing and Cryptography, DI-
MACS Series in Discrete Math and Theoretical Computer Science, American Mathe-
matical Society, 2:191--H202, 1991.
R. Rubinfeld and M. Sudan. Testing polynomial functions efficiently and over ratio-
nal domains. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete
Algorithms, pages 23--H43, 1992.
R. Rubinfeld and M. Sudan. Robust Characterizations of Polynomials and their Ap-
plications to Program Testing. Available as IBM Research Report RC 19156 (83446)
9/9/93 and Corneli CS Tech. Report 93--H1387,September 1993.
R. Zippel, personal communication, November 1993.
A Rational Domains
In this appendix, we show that the self-testers and self-correctors can be extended to rational
domains. We consider rational domains of the form Dn,s = f?s1I lil <
The theorems follow the same outline as in the finite fields case, but certain additional technical
details must be addressed. These technical details similar to those used in [GLRSW9l] [RS93].
Self-correctors. The following self-corrector works for any function satisfying Vx, y f(x) =
G[f(x --H y), f(x + y), f(y)]. Self-correctors for functions that are not solvable for f(x), but are
solvable for another of f(x --H y), f(x + y), f(y) can be similarly constructed.
As in [GLRSW91], we assume that the program has been tested over a larger domain Vm,s, in order
to self-correct over the domain Dn,s (this reqnires the more general definitions of self-correcting given
in [GLRSW91]). It suffices that m> 12n.
Program Self-Correct(x,p)
N & O(ln(1/P))
Do for i --H 1 N
Pick y ER Drn,s
answer? & G[P(x --H y), P(x + y), P(y)]
Output the most common answer in fanswer? : i = 1,...,N)
14
Theorem 17 If P (1/24)-computes f on D?,8, then Vx E Vn?, Pr[Seif --H Correct(::,P) = f(x)J >
1--HP.
The proof of this theorem follows the format ill [GLRSW91].
Proof: [of Theorem 17] By the assumption on P, P(y) is correct with?probability at least 1 --H 1
24
Two bad events can happen when picking x + y: either x + y is not in Vm,s, in which case we know
nothing about the probability that P(x + y) is correct, or z + y is in Vm,s, but happens to be one
of the inputs for which P is incorrect. By our choice of m, the first bad situation happens with
probability < 1/24. The second bad situation happens with probability < 2\ If neither of these
happens, then P(z + y) = f(x + y). The same argument can be made for P(x --H y). Thus, at each
iteration, answer? = f(x) with probability at least 1 --H 22\ --H ?W4 > 3/4. 0
Self-testers. The following is a self-tester for addition theorems over the rational domain Dm,s.
We test the program over a larger domain Vp,s in order to certify that it is usually correct over
Dm,j. It suffices that p> lim.
Program Self-Test((xo,yo),(xi,yi),. .
N O(maxf-61,481ln(2/P))
f Property Test ?
Doform=1,...,N
(1) Pick x ER Vm,s and y ER Vp,s
if P(x) $ G[P(x --H y), P(y)] output FAIL and halt
(2) Pick z, y ER Dp,a
if P(x) $ G[P(x --H y), P(y)] output FAIL and halt
(3) Pick x,y ER Dp,s
if P(x + y) $ G[P(x), P(y)J output FAIL and halt
? Equality Test J
Do for i --H 1 c
If sdfcorrector(r?, p/c) $ y? output FAIL and halt
Output PASS
Theorem 18 If P does not 1/24-compute f on Dm,s, then Pr[Self --H Test(z, P) = FAIL] > 1 --H
If P =--H f, then Self- Test outputs PASS. Thus, Self- Test is an ?-se(f-testing program for f on Vm,a.
In order to show the above theorem, we need the following theorem that shows that the addition
theorems are robust properties over rational domains.
Theorem 19 If (1) Pr:Evm,s,tiEVp,s [P(x + y) = G[P(x), P(y)]] > 1 --H 6, (2) Prx,??vps[P(X) =
G[P(x --H y), P(y)j] > 1--H6, (3) Prx,?Evp,s [P(x + y) = G[P(x), P(y)]] >1--H6, for 6<418, then there
exists a function g such that
1. Prz?vrn,.[P(Z) = 9(z)] > 1 --H 26 = 1 --H 1
24
? Vx, y E D?,j g(x + y) = G[P(x), P(y)].
15
Define g(x) to be ??jzEVp,s fG(P(z --H z), P(z))?.
The following lemma follows from the first condition 011 P and a counting argument.
Lemma 20 9 and P agree on more than 1 --H 26 fraction of the inputs from 1)in,s
For the following lemmas, set ? =
Lemma 21 For all x E D2m,s, Prz?vp,s [9(x) = G[P(x --H z), P(z)]] > 1 --H 6' where 6' = 1 --H 26 --H
Proof: For x E D2m,s, Pr??vp,sk + ? E Vp,s] > 1 --H ?. Thus,
Pry,?Evp.s [G[P(x --H y), P(y)] = G[G[P(x --H w), P(w --H ?)j, P(?)j
= G[P(x - w), G[P(w - y), P(?)]]
= G[P(x--Hw),P(w)]]			>1--H26--H2?
By the second condition on P, the first equality holds with probability 1 --H 6 --H 2? and the third
equality holds with probability 1 --H 6. The second equality always holds.
The lemma now follows from the observation that the probability that the same object is drawn
twice from a set in two independent trials lower bounds the probability of drawing the most likely
object in one trial. 0
Finally, we prove that 9 satisfies the addition theorems everywhere:
Lemma 22 For all z,y E D,n,s, g(x + y) = G[g(x),g(y)].
Proof:
Pru,vEvp,s [G[y(x),g(y)] =
G[G[P(n),P(x --H u)],G[P(v),P(?--H v)]]
G[P(u), G[P(x --H u), G[P(v), P(y --H v)]]]
G[P(u), G[G[P(x --H u), P(v)], P(y --H v)]]
C[P(u), G[P(x --H u + v), P(y --H v)]]
G[P(u), P(x + ? -
9(x+y)]
1 --H 36' --H 26 --H 3? = 1 --H 86 --H 9? > 0
By Lemma 21, the first equality holds with probability 1 --H 26' and the last equality holds with
probability 1 --H 6' (since x + ? E V2m,s). By the third assumption on P, the fourth equality holds
with probability 1--H6 --H ?. By the second assumption on P, the fifth equality holds with probability
1 --H 6 --H 2?. The other equalities always hold, due to the structure of G.
Since the statement is independent of n, v and holds with positive probability, it must hold with
probability 1. 0
16
