  In studying the expressiveness of neural networks, an important question is
whether there are functions which can only be approximated by sufficiently deep
networks, assuming their size is bounded. However, for constant depths,
existing results are limited to depths $2$ and $3$, and achieving results for
higher depths has been an important open question. In this paper, we focus on
feedforward ReLU networks, and prove fundamental barriers to proving such
results beyond depth $4$, by reduction to open problems and natural-proof
barriers in circuit complexity. To show this, we study a seemingly unrelated
problem of independent interest: Namely, whether there are polynomially-bounded
functions which require super-polynomial weights in order to approximate with
constant-depth neural networks. We provide a negative and constructive answer
to that question, by showing that if a function can be approximated by a
polynomially-sized, constant depth $k$ network with arbitrarily large weights,
it can also be approximated by a polynomially-sized, depth $3k+3$ network,
whose weights are polynomially bounded.
