On some approximation problems concerning sparse polynomials over finite fields

DOI10.1016/0304-3975(95)00162-XzbMath0871.11086MaRDI QIDQ1351508

Marek Karpinski, Igor E. Shparlinski

Publication date: 27 February 1997

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

zbMATH Keywords

polynomial time approximation algorithmlower boundsnumber of non-zeros of sparse polynomials

Mathematics Subject Classification ID

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

Related Items (7)

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 ⋮ Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines. ⋮ Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in ⋮ Deterministically testing sparse polynomial identities of unbounded degree ⋮ Zero testing of \(p\)-adic and modular polynomials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of sparse polynomial interpolation over finite fields
• The distribution of primitive roots in finite fields
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• Monte-Carlo approximation algorithms for enumeration problems
• Searching for Primitive Roots in Finite Fields
• Approximating the Number of Zeroes of a GF[2 Polynomial]
• Fast construction of irreducible polynomials over finite fields

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