The complexity of sparse polynomial interpolation over finite fields
type: Item
instance of: scholarly article
title: The complexity of sparse polynomial interpolation over finite fields
zbMATH Open document ID: 0813.11073
DOI: 10.1007/BF01438278
author: Kai Werther
published in: Applicable Algebra in Engineering, Communication and Computing
publication date: 1995-06-07T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 65D05
zbMATH DE Number: 556284
zbMATH Keywords: polynomial interpolation
zbMATH Keywords: finite fields
zbMATH Keywords: complexity
zbMATH Keywords: sparse polynomials
zbMATH Keywords: interpolation algorithm
reviewed by: Ian Blake
MaRDI profile type: Publication
cites work: On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
cites work: Applying Coding Theory to Sparse Interpolation
cites work: Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
cites work: Q5748889
cites work: Q3765876
cites work: Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$
cites work: Q3851616
cites work: Interpolating polynomials from their values
description: scientific article; zbMATH DE number 556284