  We study the polynomial approximation of symmetric multivariate functions and
of multi-set functions. Specifically, we consider $f(x_1, \dots, x_N)$, where
$x_i \in \mathbb{R}^d$, and $f$ is invariant under permutations of its $N$
arguments. We demonstrate how these symmetries can be exploited to improve the
cost versus error ratio in a polynomial approximation of the function $f$, and
in particular study the dependence of that ratio on $d, N$ and the polynomial
degree. These results are then used to construct approximations and prove
approximation rates for functions defined on multi-sets where $N$ becomes a
parameter of the input.
