On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields

DOI10.1016/0304-3975(91)90157-WzbMath0737.65002OpenAlexW1974872521MaRDI QIDQ1178687

Marek Karpinski, Johannes Grabmeier, Michael Clausen, Andreas W. M. Dress

Publication date: 26 June 1992

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

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90157-w

zbMATH Keywords

interpolationfinite fieldtime complexity\(k\)-sparse multivariate polynomialsmethod of sparse representationzero-testing

Mathematics Subject Classification ID

Related Items (19)

On learning multivariate polynomials under the uniform distribution ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Exact learning of linear combinations of monotone terms from function value queries ⋮ Sparse shifts for univariate polynomials ⋮ Learning algebraic decompositions using Prony structures ⋮ A local decision test for sparse polynomials ⋮ Almost optimal proper learning and testing polynomials ⋮ Zero testing and equation solving for sparse polynomials on rectangular domains ⋮ Sparse interpolation of multivariate rational functions ⋮ A case of depth-3 identity testing, sparse factorization and duality ⋮ Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in ⋮ Counting curves and their projections ⋮ Deterministically testing sparse polynomial identities of unbounded degree ⋮ Noisy interpolation of sparse polynomials in finite fields ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ The interpolation problem for \(k\)-sparse polynomials and character sums ⋮ Zero testing of \(p\)-adic and modular polynomials ⋮ The query complexity of finding local minima in the lattice ⋮ The complexity of sparse polynomial interpolation over finite fields

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Discrete logarithms in \(\mathrm{GF}(p)\)
• Queries and concept learning
• Parallel Algorithms for Algebraic Problems
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• A taxonomy of problems with fast parallel algorithms
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs

This page was built for publication: On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields