-discrepancy sets and their application for interpolation of sparse polynomials

DOI10.1016/0020-0190(95)00032-8MaRDI QIDQ672974zbMATH OpenOpenAlexFDO

Authors Noga Alon, Yishay Mansour

Publication date 28 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(95)00032-8

zbMATH Keywords

Analysis of algorithmsProbability analysisSparse polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Randomized interpolation and approximation of sparse polynomials stPreliminary version
• Randomized Interpolation and Approximation of Sparse Polynomials
• Sparse Polynomial Interpolation in Nonstandard Bases
• Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications
• scientific article; zbMATH DE number 871950
• A new algorithm for sparse interpolation of multivariate polynomials
• Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$
• A new deterministic algorithm for sparse multivariate polynomial interpolation
• Robust computation methods for sparse interpolation of multivariate polynomials

Cites work

• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• An Estimate for Character Sums
• Constructing Small Sets that are Uniform in Arithmetic Progressions
• Construction of a Thin Set with small Fourier Coefficients
• Improved algorithms via approximations of probability distributions (extended abstract)
• Random Cayley graphs and expanders
• Randomized interpolation and approximation of sparse polynomials stPreliminary version
• Simple Constructions of Almost k-wise Independent Random Variables

Cited in

(5)

• On the derandomization of the graph test for homomorphism over groups
• A local decision test for sparse polynomials
• Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs
• Explicit small sets with \(\varepsilon\)-discrepancy on Bohr sets
• Interpolation of polynomials given by straight-line programs

This page was built for publication: \(\varepsilon\)-discrepancy sets and their application for interpolation of sparse polynomials

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