Self-testing/correcting for polynomials and for approximate functions

Abstract

The study of self-testing/correcting programs was introduced in [8] in order to allow one to use program P to compute function f without trusting that P works correctly.A self-tester for f estimates the fraction of x for which P (x) = f (x); and a self-corrector for f takes a program that is correct on most inputs and turns it into a program that is correct on every input with high probability 1 .Both access P only as a black-box and in some precise way are not allowed to compute the function f .