On some approximation problems concerning sparse polynomials over finite fields

We obtain new lower bounds on the number of non-zeros of sparse polynomials and give a fully polynomial time (ε, δ) approximation algorithm for the number of non-zeros of multivariate sparse polynomials over a finite field of q elements and degree less than q - 1. This partially answers an open problem of D. Grigoriev and M. Karpinski. Also, probabilistic and deterministic algorithms for testing identity to zero of a sparse polynomial given by a "black-box" are given. Finally, we propose an algorithm to estimate the size of the image of a univariate sparse polynomial.