The complexity of sparse polynomial interpolation over finite fields
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.
- Sparse polynomial interpolation with finitely many values for the coefficients
- Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
- On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
- Sparse polynomial interpolation based on diversification
- Applying Coding Theory to Sparse Interpolation
- Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
- scientific article; zbMATH DE number 4023423 (Why is no real title available?)
- scientific article; zbMATH DE number 3651744 (Why is no real title available?)
- scientific article; zbMATH DE number 4182832 (Why is no real title available?)
- Interpolating polynomials from their values
- Interpolation and Approximation of Sparse Multivariate Polynomials over GF(2)
- On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
- On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
- On some approximation problems concerning sparse polynomials over finite fields
- Zero testing of \(p\)-adic and modular polynomials
- Exploring crypto dark matter: new simple PRF candidates and their applications
- Polynomial interpolation and identity testing from high powers over finite fields
- Identity testing and interpolation from high powers of polynomials of large degree over finite fields
- The interpolation problem for \(k\)-sparse polynomials and character sums
- Noisy interpolation of sparse polynomials in finite fields
- Exact learning from an honest teacher that answers membership queries
- Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix
- scientific article; zbMATH DE number 421669 (Why is no real title available?)
- Noisy Interpolation of Multivariate Sparse Polynomials in Finite Fields
- Complexity of sparse polynomial solving 2: renormalization
- Orders of Gauss periods in finite fields
- Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
- Fast interpolation of multivariate polynomials with sparse exponents
- On the decidability of sparse univariate polynomial interpolation
- Testing polynomials
- Deterministically testing sparse polynomial identities of unbounded degree
This page was built for publication: The complexity of sparse polynomial interpolation over finite fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1320441)
