Comments: File is on hadar
ContactPerson: sivak-d@cs.buffalo.edu
Remote host: regor.cs.buffalo.edu
Remote ident: sivak-d
### Begin Citation ### Do not delete this line ###
%R 96-02
%U /u1/grads/sivak-d/public_html/papers/recurrences.ps
%A Kumar, Ravi S.
%A Sivakumar, D.
%T Efficient Self-Testing of Linear Recurrences
%D January 29, 1996
%I Department of Computer Science, SUNY Buffalo
%K self-testing, recurrences, polynomials
%X We consider the problem of designing efficient self-testers for linear
recurrences, and present a complete package of self-testers for this class
of functions.  The results are proved by demonstrating an efficient
reduction from this problem to the problem of testing linear functions over
certain matrix groups.  Our tools include spectral analysis of matrices over
finite fields, and various counting arguments that extend known techniques.
The matrix twist yields completely new self-testers for polynomials over the
finite field Z/p.  The efficiency of our polynomial self-testers is better
than all previously known testers, and in the univariate case, we are able
to match the efficiency of the Blum-Luby-Rubinfeld linearity tester.  We
also present self-testers for convolution identities over groups, and
improved self-testers for polynomials over rational domains.