Expressivity of neural networks, how much information can be stored
You're probably not going to get a theoretical answer, because analyzing exactly what set of functions can be computed by a particular neural network is messy.  Or, at least, you probably won't get a tight analysis.  There are theorems showing that neural networks are universal approximators, meaning that given sufficient capacity it is possible to express every function, but this doesn't tell you the minimize size needed to express every function; it just tells you that there exists a size that is large enough.
However, if you're willing to accept empirical evidence rather than theorems and proofs, research has demonstrated empirically that if you choose a deep neural network architecture with sufficient capacity and you train for long enough, neural nets can memorize the training set and achieve 100% accuracy on the training set, at least for a randomly chosen function $f$ [1].  This may not tell you exactly what size neural network you need to ensure that it can express all such functions, and it's not a proof or a guarantee.
The VC dimension is beautiful theory but it's not clear it has a great deal of relevance to modern use of neural networks in practice.
[1] Understanding deep learning requires rethinking generalization.  Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, Oriol Vinyals.  arXiv:1611.03530