On some approximation problems concerning sparse polynomials over finite fields

DOI10.1016/0304-3975(95)00162-XMaRDI QIDQ1351508zbMATH OpenFDO

Authors Marek Karpinski, Igor E. Shparlinski

Publication date 27 February 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(95)00162-X

zbMATH Keywords

lower boundsnumber of non-zeros of sparse polynomialspolynomial time approximation algorithm

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Parallel algorithms in computer science (68W10)

Recommendations

• On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
• Computing sparse multiples of polynomials
• Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications

Cites work

• Approximating the Number of Zeroes of a GF[2] Polynomial
• Fast construction of irreducible polynomials over finite fields
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• scientific article; zbMATH DE number 429512 (Why is no real title available?)
• scientific article; zbMATH DE number 4182832 (Why is no real title available?)
• scientific article; zbMATH DE number 4185767 (Why is no real title available?)
• Monte-Carlo approximation algorithms for enumeration problems
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• Searching for Primitive Roots in Finite Fields
• The complexity of sparse polynomial interpolation over finite fields
• The distribution of primitive roots in finite fields

Cited in

(18)

• Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines.
• On the zeros of Boolean polynomials
• Zero testing of \(p\)-adic and modular polynomials
• Computing sparse multiples of polynomials
• Sparse polynomial equations and other enumerative problems whose Galois groups are wreath products
• Sparse univariate polynomials with many roots over finite fields
• Exact learning from an honest teacher that answers membership queries
• On the number of distinct roots of a lacunary polynomial over finite fields
• Erratum: ``On the heuristic of approximating polynomials over finite fields by random mappings
• Computing sparse multiples of polynomials
• Recovering zeros of polynomials modulo a prime
• Sparsity of the intersection of polynomial images of an interval
• Interpolation and Approximation of Sparse Multivariate Polynomials over GF(2)
• Approximating the Number of Zeroes of a GF[2] Polynomial
• Sparse polynomial approximation in finite fields
• Zero testing and equation solving for sparse polynomials on rectangular domains
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• Deterministically testing sparse polynomial identities of unbounded degree

This page was built for publication: On some approximation problems concerning sparse polynomials over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1351508)