  In the Random Subset Sum Problem, given $n$ i.i.d. random variables $X_1,
..., X_n$, we wish to approximate any point $z \in [-1,1]$ as the sum of a
suitable subset $X_{i_1(z)}, ..., X_{i_s(z)}$ of them, up to error
$\varepsilon$. Despite its simple statement, this problem is of fundamental
interest to both theoretical computer science and statistical mechanics. More
recently, it gained renewed attention for its implications in the theory of
Artificial Neural Networks. An obvious multidimensional generalisation of the
problem is to consider $n$ i.i.d. $d$-dimensional random vectors, with the
objective of approximating every point $\mathbf{z} \in [-1,1]^d$. In 1998, G.
S. Lueker showed that, in the one-dimensional setting, $n=\mathcal{O}(\log
\frac 1\varepsilon)$ samples guarantee the approximation property with high
probability.In this work, we prove that, in $d$ dimensions, $n =
\mathcal{O}(d^3\log \frac 1\varepsilon \cdot (\log \frac 1\varepsilon + \log
d))$ samples suffice for the approximation property to hold with high
probability. As an application highlighting the potential interest of this
result, we prove that a recently proposed neural network model exhibits
universality: with high probability, the model can approximate any neural
network within a polynomial overhead in the number of parameters.
