Download or read book Efficient Approximation Algorithms for Sparse Polynomials Over Finite Fields written by International Computer Science Institute and published by . This book was released on 1994 with total page 20 pages. Available in PDF, EPUB and Kindle. Book excerpt: Abstract: "We obtain new lower bounds on the number of non zeros of sparse polynomials and give a fully polynomial time ([eta], [delta]) 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 answers partially to 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."