Noisy Interpolation of Multivariate Sparse Polynomials in Finite Fields

摘要

We consider the problem of recovering an unknown sparse multivariate polynomial f∈F_p[X_1, ..., X_m] over a finite field F_p of prime order p from approximate values of f(t_1, ..., t_m) at polynomially many points (t_1, ..., t_m)∈(F_p)~m selected uniformly at random. Our result is based on a combination of bounds on exponential sums with the lattice reduction technique.