A local decision test for sparse polynomials
An l-sparse (multivariate) polynomial is a polynomial containing at most l-monomials in its explicit description. We assume that a polynomial is implicitly represented as a black-box: on an input query from the domain, the black-box replies with the evaluation of the polynomial at that input. We provide an efficient, randomized algorithm, that can decide whether a polynomial f : F(q)(n) -> F(q) given as a black-box is l-sparse or not, provided that q is large compared to the polynomial's total degree. The algorithm makes only O(l) queries, which is independent of the domain size. The running time of our algorithm (in the bit-complexity model) is poly(n, log d, l), where d is an upper bound on the degree of each variable. Existing interpolation algorithms for polynomials in the same model run in time poly(n, d, l). We provide a similar test for polynomials with integer coefficients. (C) 2010 Elsevier B.V. All rights reserved.
randomized algorithms sparsity tests multivariate polynomials