Checking approximate computations of polynomials and functional equations

Citation
F. Ergun et al., Checking approximate computations of polynomials and functional equations, SIAM J COMP, 31(2), 2001, pp. 550-576
Citations number
35
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
2
Year of publication
2001
Pages
550 - 576
Database
ISI
SICI code
0097-5397(20011011)31:2<550:CACOPA>2.0.ZU;2-J
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 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.