I. Shparlinski. Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, page 209--215. New York, NY, USA, ACM, (2001)
DOI: 10.1145/380752.380803
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) \F_pX with at most $m$ non-zero terms from approximate values of f(t) at polynomially many points t \F_p selected uniformly at random. The case of a polynomial f(X) = &agr; 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.
%0 Conference Paper
%1 Shparlinski:2001:SPA:380752.380803
%A Shparlinski, Igor E.
%B Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing
%C New York, NY, USA
%D 2001
%I ACM
%K Polynomapproximation endlische_Körper
%P 209--215
%R 10.1145/380752.380803
%T Sparse Polynomial Approximation in Finite Fields
%U http://doi.acm.org/10.1145/380752.380803
%X 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) \F_pX with at most $m$ non-zero terms from approximate values of f(t) at polynomially many points t \F_p selected uniformly at random. The case of a polynomial f(X) = &agr; 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.
%@ 1-58113-349-9
@inproceedings{Shparlinski:2001:SPA:380752.380803,
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) \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) = &agr; 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.},
acmid = {380803},
added-at = {2014-01-07T12:21:42.000+0100},
address = {New York, NY, USA},
author = {Shparlinski, Igor E.},
biburl = {https://www.bibsonomy.org/bibtex/284ce11fb647b09b7477bc16c6fd50d55/keinstein},
booktitle = {Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing},
doi = {10.1145/380752.380803},
interhash = {b5af29c215dac20934aea6526c5e963d},
intrahash = {84ce11fb647b09b7477bc16c6fd50d55},
isbn = {1-58113-349-9},
keywords = {Polynomapproximation endlische_Körper},
location = {Hersonissos, Greece},
numpages = {7},
pages = {209--215},
publisher = {ACM},
series = {STOC '01},
timestamp = {2014-01-07T12:21:42.000+0100},
title = {Sparse Polynomial Approximation in Finite Fields},
url = {http://doi.acm.org/10.1145/380752.380803},
year = 2001
}