Noisy interpolation of sparse polynomials in finite fields (Q2491980)

This paper gives a polynomial time algorithm for the sparse noisy interpolation problem: recover an unknown polynomial of weight at most \(w\): \[ f(x)=\sum_{j=1}^w a_jx^{e_j}\in \mathbb F_p[x], \] with the \(e_j\) known, from approximate values of \(f(t)\) at polynomially many points \(t\in\mathbb F_p\) selected uniformly at random. The case \(f(x)=ax\) is the hidden number problem introduced by Boneh and Venkatesan. The proposed algorithm extends a previous one of the first author, valid in small degrees, to cover polynomials of large (but bounded) degree. The new approach was motivated by by Waring's problem.