Robust Characterizations of Polynomials with Applications to Program Testing

The study of self-testing and self-correcting programs leads to the search for robust characterizations of functions. Here we make this notion precise and show such a characterization for polynomials. From this characterization, we get the following applications. We construct simple and efficient self-testers for polynomial functions. Our characterizations provide results in the area of coding theory, by giving extremely fast and efficient error-detecting schemes for some well known codes. This error-detection scheme plays a crucial role in subsequent results on the hardness of approximating some NP-optimization problems. 1 Introduction The study of program checkers [Blu88][BK89], self-testing programs [BLR90] and self-correcting programs [BLR90][Lip91] was introduced in order to allow one to use a program P to compute a function without trusting that P works correctly. A program checker checks that the program gives the correct answer on a particular input, a self-testing program for...