Randomized Interpolation and Approximation of Sparse Polynomials
From MaRDI portal
Publication:4834385
DOI10.1137/S0097539792239291zbMath0826.65005MaRDI QIDQ4834385
Publication date: 2 November 1995
Published in: SIAM Journal on Computing (Search for Journal in Brave)
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
