%U /u1/grads/sivak-d/tr.ps
%A S. Ravikumar
%A D. Sivakumar
%T On Self-Testing without the Generator Bottleneck
%R 95-43
%D September 20, 1995
%I Department of Computer Science, SUNY Buffalo
%X Suppose P is a program designed to compute a linear function f on a 
group G.  The task of "self-testing" f, that is, testing if P computes 
f correctly on most inputs, usually involves checking if P computes f 
correctly on all the generators of G.  Recently, F. Ergun presented 
self-testers that avoid this "generator bottleneck" for specific 
functions. In this paper, we generalize Ergun's results, and extend 
them to a much larger class of functions Our results give efficient 
self-testers for polynomial differentiation, integration, arithmetic 
in large finite field extensions, and constant-degree polynomials over 
large rings.