| Self-Testing Without The Generator Bottleneck (2002) | |||||||||||||||||
Abstract | |||||||||||||||||
| Suppose P is a program designed to compute a function f defined on a group G. The task of self-testing P , that is, testing if P computes f correctly on most inputs, usually involves testing explicitly if P computes f correctly on every generator of G. In the case of multivariate functions, the number of generators, and hence the number of such tests, becomes prohibitively large. We refer to this problem as the generator bottleneck . We develop a technique that can be used to overcome the generator bottleneck for functions that have a certain nice structure, specifically if the relationship between the values of the function on the set of generators is easily checkable. Using our technique, we build the first efficient self-testers for many linear, multilinear, and some non-linear functions. This includes the FFT, and various polynomial functions. All of the self-testers we present make only O(1) calls to the program that is being tested. As a consequence of our techniques, we also obtain efficient program result-checkers for all these problems. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||