Randomized Interpolation and Approximation of Sparse Polynomials

DOI10.1137/S0097539792239291zbMath0826.65005MaRDI QIDQ4834385

Yishay Mansour

Publication date: 2 November 1995

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

randomized algorithmmultivariate polynomialssparse polynomialsrandomized interpolation

Mathematics Subject Classification ID

Numerical interpolation (65D05) Approximation by polynomials (41A10)

Related Items

Black-box polynomial resultants, On learning multivariate polynomials under the uniform distribution, Improved sparse Fourier approximation results: Faster implementations and stronger guarantees, Book Review: A mathematical introduction to compressive sensing, Sparse polynomial interpolation based on derivatives, Sparse shifts for univariate polynomials, Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs, A local decision test for sparse polynomials, A multivariate generalization of Prony's method, Efficiently testing sparse \(\text{GF}(2)\) polynomials, Rapidly computing sparse Legendre expansions via sparse Fourier transforms, Symbolic-numeric sparse interpolation of multivariate polynomials, Combinatorial sublinear-time Fourier algorithms, Cryptographic hardness for learning intersections of halfspaces, On interpolating arithmetic read-once formulas with exponentiation, Interpolation of polynomials given by straight-line programs, Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit, Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis, A multiscale sub-linear time Fourier algorithm for noisy data