\(\varepsilon\)-discrepancy sets and their application for interpolation of sparse polynomials

DOI10.1016/0020-0190(95)00032-8zbMath0875.68534OpenAlexW2040890430MaRDI QIDQ672974

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)

Related Items (5)

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

Cites Work

• Unnamed Item
• Improved algorithms via approximations of probability distributions (extended abstract)
• Construction of a Thin Set with small Fourier Coefficients
• An Estimate for Character Sums
• Simple Constructions of Almost k-wise Independent Random Variables
• Random Cayley graphs and expanders
• Constructing Small Sets that are Uniform in Arithmetic Progressions
• Randomized interpolation and approximation of sparse polynomials stPreliminary version

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