On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields (Q1178687)

The method of sparse representation, i.e. representing a polynomial by a list of records containing a nonzero coefficient and the corresponding exponent is proved to be very successful. In this paper the authors consider these methods and problems for \(k\)-sparse multivariate polynomials over finite field \(K\) with essentially no restriction on the degree of the polynomials. Several strategies are known already for polynomials over fields of characteristic zero. The equally important, but more complicated case of a finite field \(K\) of small characteristic is studied in this paper. The result is that the time complexity of such strategies depends on the degree of the extension fields of \(K\) from which the arguments are to be chosen.