epsilon-Discrepancy Sets and Their Application for Interpolation of Sparse Polynomials

Noga Alon, Yishay MansourInf. Process. Lett 1995 · DOI · OpenReview

Abstract

We present a simple explicit construction of a probability distribution supported on (p − 1)2 vectors in Zpn, where p ⩾ n/ϵ is a prime, for which the absolute value of each nontrivial Fourier coefficients is bounded by ϵ. This construction is used to derandomize the algorithm of Mansour (1992) that interpolates a sparse polynomial in polynomial time in the bit complexity model.
BibTeX
@article{alon1995epsilon,
  author = {Noga Alon and Yishay Mansour},
  title = {{epsilon-Discrepancy Sets and Their Application for Interpolation of Sparse Polynomials}},
  journal = {Inf. Process. Lett.},
  year = {1995},
  doi = {10.1016/0020-0190(95)00032-8},
}

Loading related content...

Figure