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 language | English |
---|---|
Pages (from-to) | 209-215 |
Number of pages | 7 |
Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |
Volume | 2001 |
DOIs | |
Publication status | Published - 2001 |
Event | 33rd ACM Symposium on Theory of Computing - Crete, Greece Duration: 6 Jul 2001 → 8 Jul 2001 |
Keywords
- Exponential sums
- Finite fields
- Sparse polynomials