A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
The study of self-testing and self-correcting programs leads to the search for robust characterizations of functions. Here the authors make this notion precise and show such a characterization for polynomials. From this characterization, the authors get the following applications. Simple and efficient self-testers for polynomial functions are constructed. The 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.
A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
Yvonne Anne Pignolet, Stefan Schmid, et al.
Discrete Mathematics and Theoretical Computer Science
B.K. Boguraev, Mary S. Neff
HICSS 2000
Alessandro Morari, Roberto Gioiosa, et al.
IPDPS 2011