Testing multivariate linear functions
Funda Ergün · 1995
Self-testing programs are an approach to the problem of program correctness [BLR90].One can construct selftesters by exploiting the set of properties that uniquely define the function and test that they hold at random inputs.The existing methods become more costly in the case of multivariate functions, since the number of such properties grows infeasibly large.In this paper we develop techniques for finding a much smaller set of such properties.These lead to more efficient testers for multivariate linear functions.We present efficient self-testers for the following functions that did not have self-testers before: Fast Fourier Transform (both directions), evaluation of polynomials, dot product (and therefore vector 2-norm), and pointwise evaluation of linear functions on vectors (and some non-linear ones as well).We present a tester for polynomial multiplication that makes O(1) calls to the program, in contrast to O(log n) of the existing tester, and present a new tester for matrix multiplication.All of the testers presented make O(1) calls to the program that is being tested.