Authors

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.