TY - JOUR
T1 - Noisy interpolation of sparse polynomials in finite fields
AU - Shparlinski, Igor
AU - Winterhof, Arne
PY - 2005/12
Y1 - 2005/12
N2 - We consider a polynomial analogue of the hidden number problem introduced by Boneh and Venkatesan, namely the sparse polynomial noisy interpolation problem of recovering an unknown polynomial f(X) [InlineMediaObject not available: see fulltext.][X] with at most w non-zero terms from approximate values of f(t) at polynomially many points t [InlineMediaObject not available: see fulltext.] selected uniformly at random. We extend the polynomial time algorithm of the first author for polynomials f(X) of sufficiently small degree to polynomials of almost arbitrary degree. Our result is 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. The new idea is motivated by Waring's problem and uses a recent bound on exponential sums of Cochrane, Pinner, and Rosenhouse.
AB - We consider a polynomial analogue of the hidden number problem introduced by Boneh and Venkatesan, namely the sparse polynomial noisy interpolation problem of recovering an unknown polynomial f(X) [InlineMediaObject not available: see fulltext.][X] with at most w non-zero terms from approximate values of f(t) at polynomially many points t [InlineMediaObject not available: see fulltext.] selected uniformly at random. We extend the polynomial time algorithm of the first author for polynomials f(X) of sufficiently small degree to polynomials of almost arbitrary degree. Our result is 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. The new idea is motivated by Waring's problem and uses a recent bound on exponential sums of Cochrane, Pinner, and Rosenhouse.
UR - http://www.scopus.com/inward/record.url?scp=33645282569&partnerID=8YFLogxK
U2 - 10.1007/s00200-005-0180-1
DO - 10.1007/s00200-005-0180-1
M3 - Article
AN - SCOPUS:33645282569
VL - 16
SP - 307
EP - 317
JO - Applicable Algebra in Engineering, Communications and Computing
JF - Applicable Algebra in Engineering, Communications and Computing
SN - 0938-1279
IS - 5
ER -