Sparse polynomial approximation in finite fields

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) \in \F_p[X] with at most $m$ non-zero terms from approximate values of f(t) at polynomially many points t \in \F_p 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.

Authors

• Igor E. Shparlinski

Keywords

• exponential sums
• finite fields
• sparse polynomials