Noisy polynomial interpolation modulo prime powers (Q2034569)

The paper gives a deterministic polynomial time algorithm for the sparse polynomial noisy interpolation problem over residue rings: recover an unknown \(s\)-sparse polynomial \[ f(X)=\sum_{j=1}^{s}a_jX^{e_j} \in \mathbb{Z}_m[X], \] with the degrees \(e_j\) known, from approximate values of \(f(t)\) at polynomially many points \(t\in\mathbb{Z}_m\) selected uniformly at random. The case of a linear polynomial \(f(X)=aX\) with unknown \(a\) is the so-called hidden number problem, introduced by Boneh and Venkatesan, that have already been studied intensively. The authors consider the case when \(m=p^k\) is a large power of a fixed small prime, which is the new setting. The results are based on the previous works of the second author on sparse polynomial interpolation over finite fields of prime order and on bounds on exponential sums with sparse polynomials and the lattice reduction technique. The paper was motivated by increasing interest in algorithms for polynomials over residue rings modulo prime powers.