Sparse polynomial approximation in finite fields

Igor Shparlinski*

*Corresponding author for this work

Research output: Contribution to journalConference paper

22 Citations (Scopus)

Abstract

We consider a polynomial analogue of the hidden number problem which has recently been introduced by Boneh and Venkatesan. Namely we consider the sparse polynomial approximation problem of recovering an unknown polynomial f(X) ∈ IFp[X] with at most m non-zero terms from approximate values of f(t) at polynomially many points t ∈ IFp selected uniformly at random. The case of a polynomial f(X) = αX corresponds to the hidden number problem. The above problem is related to the noisy polynomial interpolation problem and to the sparse polynomial interpolation problem which have recently been considered in the literature. Our results are based on a combination of some number theory tools such as bounds of exponential sums and the number of solutions of congruences with the lattice reduction technique.
Original languageEnglish
Pages (from-to)209-215
Number of pages7
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
Volume2001
DOIs
Publication statusPublished - 2001
Event33rd ACM Symposium on Theory of Computing - Crete, Greece
Duration: 6 Jul 20018 Jul 2001

Keywords

  • Exponential sums
  • Finite fields
  • Sparse polynomials

Fingerprint Dive into the research topics of 'Sparse polynomial approximation in finite fields'. Together they form a unique fingerprint.

Cite this