Self-testing without the generator bottleneck

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 o n most inputs, usually involves testing explicitly if P computes f correctl y on every generator of G. In the case of multivariate functions, the numbe r of generators, and hence the number of such tests, becomes prohibitively large. We refer to this problem as the generator bottleneck. We develop a t echnique that can be used to overcome the generator bottleneck for function s that have a certain nice structure, specifically if the relationship betw een 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 l inear, multilinear, and some nonlinear functions. This includes the FFT, an d various polynomial functions. All of the self-testers we present make onl y O(1) calls to the program that is being tested. As a consequence of our t echniques, we also obtain efficient program result-checkers for all these p roblems.