On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields

Clausen M, Dress A, Grabmeier J, Karpinski M (1991)
Theoretical Computer Science 84(2): 151-164.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Clausen, Michael; Dress, AndreasUniBi; Grabmeier, Johannes; Karpinski, Marek
Abstract / Bemerkung
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 2log n.log k queries are needed.
Erscheinungsjahr
1991
Zeitschriftentitel
Theoretical Computer Science
Band
84
Ausgabe
2
Seite(n)
151-164
ISSN
0304-3975
Page URI
https://pub.uni-bielefeld.de/record/1649577

Zitieren

Clausen M, Dress A, Grabmeier J, Karpinski M. On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields. Theoretical Computer Science. 1991;84(2):151-164.
Clausen, M., Dress, A., Grabmeier, J., & Karpinski, M. (1991). On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields. Theoretical Computer Science, 84(2), 151-164. https://doi.org/10.1016/0304-3975(91)90157-W
Clausen, M., Dress, A., Grabmeier, J., and Karpinski, M. (1991). On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields. Theoretical Computer Science 84, 151-164.
Clausen, M., et al., 1991. On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields. Theoretical Computer Science, 84(2), p 151-164.
M. Clausen, et al., “On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields”, Theoretical Computer Science, vol. 84, 1991, pp. 151-164.
Clausen, M., Dress, A., Grabmeier, J., Karpinski, M.: On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields. Theoretical Computer Science. 84, 151-164 (1991).
Clausen, Michael, Dress, Andreas, Grabmeier, Johannes, and Karpinski, Marek. “On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields”. Theoretical Computer Science 84.2 (1991): 151-164.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Suchen in

Google Scholar