The complexity of sparse polynomial interpolation over finite fields

DOI10.1007/BF01438278MaRDI QIDQ1320441zbMATH OpenFDO

Authors Kai Werther

Publication date 7 June 1995

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

zbMATH Keywords

complexityfinite fieldspolynomial interpolationsparse polynomialsinterpolation algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical interpolation (65D05) Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• 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

Cites work

• 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?)
• Applying Coding Theory to Sparse Interpolation
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• 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

Cited in

(18)

• Orders of Gauss periods in finite fields
• Exploring crypto dark matter: new simple PRF candidates and their applications
• Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix
• Complexity of sparse polynomial solving 2: renormalization
• Exact learning from an honest teacher that answers membership queries
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• Noisy interpolation of sparse polynomials in finite fields
• Noisy Interpolation of Multivariate Sparse Polynomials in Finite Fields
• Testing polynomials
• Identity testing and interpolation from high powers of polynomials of large degree over finite fields
• Deterministically testing sparse polynomial identities of unbounded degree
• The interpolation problem for \(k\)-sparse polynomials and character sums
• Fast interpolation of multivariate polynomials with sparse exponents
• scientific article; zbMATH DE number 421669 (Why is no real title available?)
• Zero testing of \(p\)-adic and modular polynomials
• Polynomial interpolation and identity testing from high powers over finite fields
• On some approximation problems concerning sparse polynomials over finite fields
• On the decidability of sparse univariate polynomial interpolation

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)