Randomized interpolation and approximation of sparse polynomials stPreliminary version

DOI10.1007/3-540-55719-9_79zbMATH Open1427.65013OpenAlexW2205422138MaRDI QIDQ5204322FDOQ5204322

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

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

zbMATH Keywords

randomized algorithmmultivariate polynomialssparse polynomialsrandomized interpolation

Mathematics Subject Classification ID

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

Cites Work

• Learning Decision Trees Using the Fourier Spectrum
• Title not available (Why is that?)
• A guided tour of Chernoff bounds
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• Title not available (Why is that?)

Cited In (10)

• Title not available (Why is that?)
• A deterministic sparse FFT for functions with structured Fourier sparsity
• \(\varepsilon\)-discrepancy sets and their application for interpolation of sparse polynomials
• Title not available (Why is that?)
• Sparsified randomization algorithms for low rank approximations and applications to integral equations and inhomogeneous random field simulation
• Private multiparty sampling and approximation of vector combinations
• Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time
• An explicit separation of relativised random polynomial time and relativised deterministic polynomial time
• Finding significant Fourier coefficients: clarifications, simplifications, applications and limitations
• Randomized Interpolation and Approximation of Sparse Polynomials

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)