Efficient Approximation Algorithms for Sparse Polynomials over Finite Fields
| Title | Efficient Approximation Algorithms for Sparse Polynomials over Finite Fields |
| Publication Type | Technical Report |
| Year of Publication | 1994 |
| Authors | Karpinski, M., & Shparlinski I. |
| Other Numbers | 899 |
| Abstract | We obtain new lower bounds on the number of non zeros of sparse polynomials and give a fully polynomial time (e,d) 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. Grivoriev 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. |
| URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1994/tr-94-029.pdf |
| Bibliographic Notes | ICSI Technical Report TR-94-029 |
| Abbreviated Authors | M. Karpinski and I. Shparlinski |
| ICSI Publication Type | Technical Report |