-discrepancy sets and their application for interpolation of sparse polynomials

DOI10.1016/0020-0190(95)00032-8zbMATH Open0875.68534OpenAlexW2040890430MaRDI QIDQ672974FDOQ672974

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

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

zbMATH Keywords

Analysis of algorithmsProbability analysisSparse polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

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

Cited In (5)

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