Robust Functional Equations with Applications to Self-Testing/Correcting

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.