Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1985-1989 Copyright 1985-1989 University of Bonn, Department of Computer Science, Abt. V
8522

01.12.2008

On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials over Finite Fields
Michael Clausen, Andreas Dress, Johannes Grabmeier and Marek Karpinski
[Download PostScript] [Download PDF]

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 each 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 filed K is studied in the present paper. The result is that the time complexity of such strategies depends critically on the degree of m of the extension filed 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.

Last Change: 12/01/08 at 19:06:02
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V