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 noti on of correctness and show how to check programs that compute only a numeri cal approximation to the correct answer. The types of programs that we deal with are those computing polynomials and functions defined by certain type s of functional equations. We present results showing how to perform approx imate 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. Rubinfel d and M. Sudan, Proceedings of the Third Annual ACM-SIAM Symposium on Discr ete Algorithms, Orlando, FL, 1992, pp. 23-43; R. Rubinfeld and M. Sudan, SI AM J. Comput., 25 (1996), pp. 252-271]. We obtain this by rst building appr oximate self-testers for linear and multilinear functions. We then show how to perform approximate checking, self-testing, and self-correcting for tho se functions that satisfy addition theorems, settling a question raised by [R. Rubinfeld, SIAM J. Comput., 28 (1999), pp. 1972-1997]. In both cases, w e show that the properties used to test programs for these functions are bo th robust ( in the approximate sense) and stable. Finally, we explore the u se of reductions between functional equations in the context of approximate self-testing. Our results have implications for the stability theory of fu nctional equations.