| Approximate Checking of Polynomials and Functional Equations (1998) | |||||||||||||||
Abstract | |||||||||||||||
| In this paper, we show how to check programs that compute polynomials and functions defined by addition theorems --- in the realistic setting where the output of the program is approximate instead of exact. We present results showing how to perform approximate checking, self-testing, and self-correcting of polynomials, settling in the affirmative a question raised by [GLR + 91, RS92, RS96]. 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 [Rub94]. In both cases, we show that the properties used to test programs for these functions are both This work is partially supported by NSF Career grant CCR-9624552, the Alfred P. Sloan Research Award, and ONR grant N00014-97-1-0505. The first and second authors are also supported by NSF grant DMI-91157199. The third author is also su... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||