| Checking Approximate Computations of Polynomials and Functional Equations (2000) | |||||||||||||||||
Abstract | |||||||||||||||||
| A majority of the results on self-testing and correcting deal with programs which purport to compute the correct results precisely. In this paper, we observe that this notion of correctness is too strict for a number of reasons, and show how to check programs which are expected to compute an answer which is close 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 armative a question raised by [GLR + 91, RS92, RS96]. We obtain this by first building approximate self-testers for linear and multilinear functions. We then... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||