THE POWER OF DEEPER NETWORKS FOR EXPRESSING NATURAL FUNCTIONS
It is well-known that neural networks are universal approximators, but that deeper networks tend in practice to be more powerful than shallower ones. We shed light on this by proving that the total number of neurons m required to approximate natural classes of multivariate polynomials of n variables grows only linearly with n for deep neural networks, but grows exponentially when merely a single hidden layer is allowed. We also provide evidence that when the number of hidden layers is increased from 1 to k, the neuron requirement grows exponentially not with n but with n 1/k , suggesting that the minimum number of layers required for practical expressibility grows only logarithmically with n.
The paper investigates the representation of polynomials by neural networks up to a certain degree and implied uniform approximations. It shows exponential gaps between the width of shallow and deep networks required for approximating a given sparse polynomial. 
By focusing on polynomials, the paper is able to use of a variety of tools (e.g. linear algebra) to investigate the representation question. Results such as Proposition 3.3 relate the representation of a polynomial up to a certain degree, to the approximation question. Here it would be good to be more specific about the domain, however, as approximating the low order terms certainly does not guarantee a global uniform approximation. 
Theorem 3.4 makes an interesting claim, that a finite network size is sufficient to achieve the best possible approximation of a polynomial (the proof building on previous results, e.g. by Lin et al that I did not verify). The idea being to construct a superposition of Taylor approximations of the individual monomials. Here it would be good to be more specific about the domain. Also, in the discussion of Taylor series, it would be good to mention the point around which the series is developed, e.g. the origin. 
The paper mentions that ``the theorem is false for rectified linear units (ReLUs), which are piecewise linear and do not admit a Taylor series''. However, a ReLU can also be approximated by a smooth function and a Taylor series. 
Theorem 4.1 seems to be implied by Theorem 4.2. Similarly, parts of Section 4.2 seem to follow directly from the previous discussion. 
In page 1 ```existence proofs' without explicit constructions'' This is not true, with numerous papers providing explicit constructions of functions that are representable by neural networks with specific types of activation functions.