ϵ-discrepancy sets and their application for interpolation of sparse polynomials

Noga Alon, Yishay Mansour

Research output: Contribution to journalArticle

20 Scopus citations

Abstract

We present a simple explicit construction of a probability distribution supported on (p - 1)2 vectors in Zpn, where p ≥ n/ε{lunate} is a prime, for which the absolute value of each nontrivial Fourier coefficients is bounded by ε{lunate}. This construction is used to derandomize the algorithm of Mansour (1992) that interpolates a sparse polynomial in polynomial time in the bit complexity model.

Original languageEnglish (US)
Pages (from-to)337-342
Number of pages6
JournalInformation Processing Letters
Volume54
Issue number6
DOIs
StatePublished - Jun 23 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Analysis of algorithms
  • Probability analysis
  • Sparse polynomials

Fingerprint Dive into the research topics of 'ϵ-discrepancy sets and their application for interpolation of sparse polynomials'. Together they form a unique fingerprint.

  • Cite this