Randomized interpolation and approximation of sparse polynomials stPreliminary version

DOI10.1007/3-540-55719-9_79MaRDI QIDQ5204322zbMATH OpenOpenAlexFDO

Authors Yishay Mansour

Publication date 4 December 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-55719-9_79

zbMATH Keywords

multivariate polynomialsrandomized algorithmrandomized interpolationsparse polynomials

Mathematics Subject Classification ID

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

Recommendations

• Randomized Interpolation and Approximation of Sparse Polynomials
• Revisit sparse polynomial interpolation based on randomized Kronecker substitution
• A new algorithm for sparse interpolation of multivariate polynomials
• A new deterministic algorithm for sparse multivariate polynomial interpolation
• Sparse Polynomial Interpolation in Nonstandard Bases
• Robust algorithms for sparse interpolation of multivariate polynomials
• Robust computation methods for sparse interpolation of multivariate polynomials
• scientific article; zbMATH DE number 1273635
• Sparse polynomial interpolation based on diversification
• Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs

Cites work

• A guided tour of Chernoff bounds
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 4182832 (Why is no real title available?)
• Learning Decision Trees Using the Fourier Spectrum

Cited in

(11)

• Private multiparty sampling and approximation of vector combinations
• A deterministic sparse FFT for functions with structured Fourier sparsity
• Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time
• Sparsified randomization algorithms for low rank approximations and applications to integral equations and inhomogeneous random field simulation
• Finding significant Fourier coefficients: clarifications, simplifications, applications and limitations
• Randomized Interpolation and Approximation of Sparse Polynomials
• Estimating the frequency of a clustered signal
• scientific article; zbMATH DE number 7053345 (Why is no real title available?)
• -discrepancy sets and their application for interpolation of sparse polynomials
• Deterministic sparse Fourier transform with an _ guarantee
• An explicit separation of relativised random polynomial time and relativised deterministic polynomial time

This page was built for publication: Randomized interpolation and approximation of sparse polynomials stPreliminary version

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