Checking approximate computations of polynomials and functional equations

Abstract

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. © 2001 Society for Industrial and Applied Mathematics.