@Inproceedings {export:204625,
abstract = {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.

},
author = {Alexandr Andoni and Rina Panigrahy and Gregory Valiant and Li Zhang},
booktitle = {SODA},
publisher = {ACM},
title = {Learning sparse polynomials},
url = {http://research.microsoft.com/apps/pubs/default.aspx?id=204625},
year = {2014},
}