| Approximate Checking of Polynomials and Functional Equations (1999) | |||||||||||||||
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 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 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. This work is partially supported by NSF Career grant CCR-9624552 and the Alfred P. Sloan Res... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||