Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
DOI10.1137/0219073zbMATH Open0711.68059OpenAlexW2113291984MaRDI QIDQ3495652FDOQ3495652
Marek Karpinski, Michael F. Singer, Dima 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
Recommendations
- scientific article; zbMATH DE number 871950
- Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications
- Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs
- Sparse polynomial interpolation based on diversification
- Sparse interpolation over finite fields via low-order roots of unity
Symbolic computation and algebraic computation (68W30) Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16)
Cited In (33)
- Sparse shifts for univariate polynomials
- Fast Hermite interpolation and evaluation over finite fields of characteristic two
- Interpolation of polynomials given by straight-line programs
- A local decision test for sparse polynomials
- Randomized interpolation and approximation of sparse polynomials stPreliminary version
- Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony?
- Counting curves and their projections
- An improved early termination sparse interpolation algorithm for multivariate polynomials
- Symbolic-numeric sparse interpolation of multivariate polynomials
- On learning multivariate polynomials under the uniform distribution
- Reconstructing Algebraic Functions from Mixed Data
- Exact learning from an honest teacher that answers membership queries
- Fast multipoint evaluation and interpolation of polynomials in the LCH-basis over F P r
- Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
- Early termination in sparse interpolation algorithms
- On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
- Zero testing and equation solving for sparse polynomials on rectangular domains
- Title not available (Why is that?)
- Title not available (Why is that?)
- Deterministically testing sparse polynomial identities of unbounded degree
- Sparse interpolation of multivariate rational functions
- An explicit separation of relativised random polynomial time and relativised deterministic polynomial time
- The interpolation problem for \(k\)-sparse polynomials and character sums
- Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases
- Efficiently testing sparse \(\text{GF}(2)\) polynomials
- Sparse polynomial interpolation based on diversification
- Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications
- Fast interpolation of multivariate polynomials with sparse exponents
- The interpolation problem for \(k\)-sparse sums of eigenfunctions of operators
- Zero testing of \(p\)-adic and modular polynomials
- Faster sparse multivariate polynomial interpolation of straight-line programs
- The complexity of sparse polynomial interpolation over finite fields
- On some approximation problems concerning sparse polynomials over finite fields
This page was built for publication: Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3495652)
