Publication Details
Title: On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials over Finite Fields
Author: M. Clausen, A. Dress, J. Grabmeier, and M. Karpinski
Group: ICSI Technical Reports
Date: July 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-46.pdf
Overview:
Given a black box which will produce the value of a k-sparse multivariate polynomial for any given specific argument, one may ask for optimal strategies (1) to distinguish such a polynomial from the zero-polynomial, (2) to distinguish any two such polynomials from one other and (3) to (uniformly) reconstruct the polynomial from such an information source. While such strategies are known already for polynomials over fields of characteristic zero, the equally important, but considerably more complicated case of a finite field K of small characteristic is studied in the present paper. The result is that the time complexity of such strategies depends critically on the degree m of the extension field of K from which the arguments are to be chosen; e.g., if m equals the number n of variables, then (1) can be solved by k+1 and (2) as well as (3) by 2k+1 queries, while in case m=1 essentially 2 (superscript log n log k) queries are needed.
Bibliographic Information:
ICSI Technical Report TR-89-046
Bibliographic Reference:
M. Clausen, A. Dress, J. Grabmeier, and M. Karpinski. On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials over Finite Fields. ICSI Technical Report TR-89-046, July 1989
Author: M. Clausen, A. Dress, J. Grabmeier, and M. Karpinski
Group: ICSI Technical Reports
Date: July 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-46.pdf
Overview:
Given a black box which will produce the value of a k-sparse multivariate polynomial for any given specific argument, one may ask for optimal strategies (1) to distinguish such a polynomial from the zero-polynomial, (2) to distinguish any two such polynomials from one other and (3) to (uniformly) reconstruct the polynomial from such an information source. While such strategies are known already for polynomials over fields of characteristic zero, the equally important, but considerably more complicated case of a finite field K of small characteristic is studied in the present paper. The result is that the time complexity of such strategies depends critically on the degree m of the extension field of K from which the arguments are to be chosen; e.g., if m equals the number n of variables, then (1) can be solved by k+1 and (2) as well as (3) by 2k+1 queries, while in case m=1 essentially 2 (superscript log n log k) queries are needed.
Bibliographic Information:
ICSI Technical Report TR-89-046
Bibliographic Reference:
M. Clausen, A. Dress, J. Grabmeier, and M. Karpinski. On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials over Finite Fields. ICSI Technical Report TR-89-046, July 1989