Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
From MaRDI portal
Publication:3495652
DOI10.1137/0219073zbMath0711.68059OpenAlexW2113291984MaRDI QIDQ3495652
Michael F. Singer, Marek Karpinski, Dima Yu. Grigoriev
Publication date: 1990
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/e2a829761094dffcd881373c6e55f3491b97334f
Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Polynomials over finite fields (11T06)
Related Items (27)
Early termination in sparse interpolation algorithms ⋮ Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases ⋮ An improved early termination sparse interpolation algorithm for multivariate polynomials ⋮ On learning multivariate polynomials under the uniform distribution ⋮ Sparse polynomial interpolation based on diversification ⋮ On some approximation problems concerning sparse polynomials over finite fields ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Sparse shifts for univariate polynomials ⋮ A local decision test for sparse polynomials ⋮ Zero testing and equation solving for sparse polynomials on rectangular domains ⋮ Sparse interpolation of multivariate rational functions ⋮ Unnamed Item ⋮ Efficiently testing sparse \(\text{GF}(2)\) polynomials ⋮ An explicit separation of relativised random polynomial time and relativised deterministic polynomial time ⋮ Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in ⋮ On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields ⋮ Counting curves and their projections ⋮ Symbolic-numeric sparse interpolation of multivariate polynomials ⋮ Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony? ⋮ Deterministically testing sparse polynomial identities of unbounded degree ⋮ Randomized interpolation and approximation of sparse polynomials stPreliminary version ⋮ The interpolation problem for \(k\)-sparse polynomials and character sums ⋮ The interpolation problem for \(k\)-sparse sums of eigenfunctions of operators ⋮ Interpolation of polynomials given by straight-line programs ⋮ Zero testing of \(p\)-adic and modular polynomials ⋮ Reconstructing Algebraic Functions from Mixed Data ⋮ The complexity of sparse polynomial interpolation over finite fields
This page was built for publication: Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
