Learning sparse polynomials

We study the question of learning a sparse multi-variate polynomial over the real domain. In particular, for some unknown polynomial f(vx ) of degree-d and k monomials, we show how to reconstruct f, within error ε, given only a set of examples bar x_i drawn uniformly from the n-dimensional cube (or an n-dimensional Gaussian distribution), together with evaluations f(bar x_i) on them. The result holds even in the “noisy setting”, where we have only values f(bar x_i)+g where g is noise (say, modeled as a Gaussian random variable). The runtime of our algorithm is polynomial in n,k,1/ε and C_d where C_d depends only on d. Note that, in contrast, in the “boolean version” of this problem, where bar x is drawn from the hypercube, the problem is at least as hard as the “noisy parity problem,” where we do not know how to break the n^Ω(d) time barrier, even for k=1, and some believe it may be impossible to do so.