Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications

DOI10.1006/JAGM.1999.1045MaRDI QIDQ4935306zbMATH OpenOpenAlexFDO

Authors Ashwin Rao, Ming-Deh A. Huang

Publication date 19 March 2000

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1999.1045

zbMATH Keywords

bit operationscomplexitydeterminantfactorizationfinite fieldgreatest common divisorinterpolationLas Vegas algorithmMonte Carlo algorithmmultivariate polynomialparallel algorithmrandomized algorithmsparse polynomial interpolation

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Parallel algorithms in computer science (68W10) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30)

Recommendations

• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• scientific article; zbMATH DE number 871950
• Sparse polynomial interpolation based on diversification
• Sparse interpolation over finite fields via low-order roots of unity
• Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs

Cited in

(31)

• On some approximation problems concerning sparse polynomials over finite fields
• Computing sparse GCD of multivariate polynomials via polynomial interpolation
• Computing sparse multiples of polynomials
• Sparse polynomial interpolation based on diversification
• Sparse polynomial interpolation based on derivatives
• Noisy interpolation of sparse polynomials in finite fields
• Faster sparse multivariate polynomial interpolation of straight-line programs
• Output-sensitive algorithms for sumset and sparse polynomial multiplication
• Computing sparse multiples of polynomials
• Multivariate sparse interpolation using randomized Kronecker substitutions
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• Noisy Interpolation of Multivariate Sparse Polynomials in Finite Fields
• Solving sparse linear equations over finite fields
• A local decision test for sparse polynomials
• scientific article; zbMATH DE number 1273635 (Why is no real title available?)
• scientific article; zbMATH DE number 503193 (Why is no real title available?)
• On the evaluation of some sparse polynomials
• Randomized Interpolation and Approximation of Sparse Polynomials
• scientific article; zbMATH DE number 799768 (Why is no real title available?)
• scientific article; zbMATH DE number 871950 (Why is no real title available?)
• On some computations on sparse polynomials
• On sparse interpolation of rational functions and gcds
• What can (and can't) we do with sparse polynomials?
• Sparse polynomial interpolation over fields with large or zero characteristic
• A sparse polynomial interpolation based on racing strategy
• scientific article; zbMATH DE number 4182832 (Why is no real title available?)
• -discrepancy sets and their application for interpolation of sparse polynomials
• Sparse interpolation of symmetric polynomials
• On the decidability of sparse univariate polynomial interpolation
• Sparse polynomial interpolation: faster strategies over finite fields
• Fast interpolation and multiplication of unbalanced polynomials

This page was built for publication: Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications

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