Exponential gap on neural network layers I read it here that there are function families which need $\mathcal{O}(2^n)$ nodes on neural network with at most $d - 1$ layers to represent the function while need only $\mathcal{O}(n)$ if the neural network has at least $d$ layers. It was referring to a paper by Hastad. I didn't find it. Could someone tell me the title of the paper? I think this is a really fascinating theoretical result.
The paper that people usually cite is Almost Optimal Lower Bounds for Small Depth Circuits, which appears in STOC 1986. The main result pertaining to your question is: 


  There exists a family of functions admitting linear size, depth $k$ circuits (of unbounded fan-in AND/OR and NOT) that requires exponential size at depth $k-1$. 


What's possible even more relevant is the fact that $\mathsf{TC}^0$ admits an exponential separation between depth 3 and depth 2. This is relevant because threshold gates are commonly used in deep networks.