JavaScript is disabled for your browser. Some features of this site may not work without it.
Robust Functional Equations with Applications to Self-Testing/Correcting

Author
Rubinfeld, Ronitt
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.
Date Issued
1994-07Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR94-1435
Type
technical report