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

complexity; finite fields; polynomial interpolation; sparse polynomials; interpolation algorithm

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

11Y16: Number-theoretic algorithms; complexity

65D05: Numerical interpolation

11T06: Polynomials over finite fields

Related Items

Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in, Deterministically testing sparse polynomial identities of unbounded degree, 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, Noisy interpolation of sparse polynomials in finite fields, Exact learning from an honest teacher that answers membership queries

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item