Randomized interpolation and approximation of sparse polynomials stPreliminary version

DOI10.1007/3-540-55719-9_79zbMath1427.65013OpenAlexW2205422138MaRDI QIDQ5204322

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

randomized algorithmmultivariate polynomialssparse polynomialsrandomized interpolation

Mathematics Subject Classification ID

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

Related Items (7)

\(\varepsilon\)-discrepancy sets and their application for interpolation of sparse polynomials ⋮ A deterministic sparse FFT for functions with structured Fourier sparsity ⋮ Unnamed Item ⋮ Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time ⋮ Private multiparty sampling and approximation of vector combinations ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• A guided tour of Chernoff bounds
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• Learning Decision Trees Using the Fourier Spectrum
• Unnamed Item
• Unnamed Item

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