We study the polynomial approximation of symmetric multivariate functions and of multi-set functions. Specifically, we consider f ( x 1 , … , x N ) f(x_1, \dots , x_N) , where x i ∈ R d x_i \in \mathbb {R}^d , and f f is invariant under permutations of its N 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 f , and in particular study the dependence of that ratio on d , N 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 N becomes a parameter of the input.