The complexity of sparse polynomial interpolation over finite fields

DOI10.1007/BF01438278zbMath0813.11073MaRDI QIDQ1320441

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) Number-theoretic algorithms; complexity (11Y16) Numerical interpolation (65D05) Polynomials over finite fields (11T06)

Related Items (7)

Exploring crypto dark matter: new simple PRF candidates and their applications ⋮ On some approximation problems concerning sparse polynomials over finite fields ⋮ 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 ⋮ Deterministically testing sparse polynomial identities of unbounded degree ⋮ Noisy interpolation of sparse polynomials in finite fields ⋮ Zero testing of \(p\)-adic and modular polynomials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Interpolating polynomials from their values
• On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
• Applying Coding Theory to Sparse Interpolation
• Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields

This page was built for publication: The complexity of sparse polynomial interpolation over finite fields