  The task of approximating a function of d variables from its evaluations at a
given number of points is ubiquitous in numerical analysis and engineering
applications. When d is large, this task is challenged by the so-called curse
of dimensionality. As a typical example, standard polynomial spaces, such as
those of total degree type, are often uneffective to reach a prescribed
accuracy unless a prohibitive number of evaluations is invested. In recent
years it has been shown that, for certain relevant applications, there are
substantial advantages in using certain sparse polynomial spaces having
anisotropic features with respect to the different variables. These
applications include in particular the numerical approximation of
high-dimensional parametric and stochastic partial differential equations. We
start by surveying several results in this direction, with an emphasis on the
numerical algorithms that are available for the construction of the
approximation, in particular through interpolation or discrete least-squares
fitting. All such algorithms rely on the assumption that the set of
multi-indices associated with the polynomial space is downward closed. In the
present paper we introduce some tools for the study of approximation in
multivariate spaces under this assumption, and use them in the derivation of
error bounds, sometimes independent of the dimension d, and in the development
of adaptive strategies.
