The complexity of sparse polynomial interpolation over finite fields (Q1320441)

The interpolation of \(n\)-variate polynomials \(f\) of degree \(d = \max \deg_{X_ i}f\) requires at least \((d+1)^ n\) evaluations of the unknown polynomial \(f\). Denote the number of nonzero coefficients of \(f\) its sparsity and call a polynomial \(k\)-sparse if its sparsity is at most \(k\). A set \(A \subseteq \mathbb{R}^ n\) is a test set if for all \(n\)-variate \(k\)-sparse polynomials \(f \neq 0\) of degree at most \(d\) there is an \(a \in A\) with \(f(a) \neq 0\). An estimate of the size of a test set constructed by \textit{M. Clausen}, \textit{A. Dress}, \textit{J. Grabmeier} and \textit{M. Karpinski} [Theor. Comput. Sci. 84, 151-164 (1991; Zbl 0737.65002)] is given and the previously known lower bounds on the size of a minimal test set are improved. A new interpolation algorithm for arbitrary fields that uses only evaluations over the ground field is given.