Self-testing polynomial functions efficiently and over rational domains
Ronitt Rubinfeld, Madhu Sudan · 1992
In this paper we give the first self-testers and checkers for polynomials over rational and integer domains. We also show significantly stronger bounds on the efficiency of a simple modification of the algorithm for self-testing polynomials over finite fields given in [8]. 1 Introduction Suppose someone gives us an extremely fast program P that we can call as a black box to compute a function f . Rather than trust that P works correctly, a self-testing program for f ([5]) verifies that program P is correct on most inputs (without assuming the correctness of another program that is as difficult as one that computes the function), and a self-correcting program ([5] [9]) for f takes a program P , that is correct on most inputs, and uses it to compute f correctly on every input (with high probability). Both access P only as a black-box and in some precise way are not allowed to compute the function f . Self-testing/correcting is an extension of program result checking as defined in [3],...