If you restrict the depth of the circuit, you can in principle represent any function, but you need a really wide (exponentially wide) circuit.
Are you sure it's exponential ?
If you look at binary functions (ie. boolean circuits) any such function can be represented by a single layer function whose size is linear in the number of gates of the original function (I think it's 3 or 4 variables per gate) by converting to conjunctive normal form.
Of course it's not obvious that a similar scaling exists for non-binary functions but I'd be a bit surprised if increasing depth led to an exponential gain in representational efficiency.
I am not sure in the sense of: If I were dropped on a desert island, I could derive a water-tight proof of this result from scratch.
I am confident, though, based upon my reading of secondary sources written by people that I trust.
From one of Bengio's works (http://www.iro.umontreal.ca/~bengioy/papers/ftml.pdf):
"More interestingly, there are functions computable with a polynomial-size logic gates circuit of depth k
that require exponential size when restricted to depth k − 1 (Hastad, 1986)."
I think my argument was mistaken. The CNF form I was thinking of involves adding unknown variables so it doesn't actually allow you to compute the function in one step.
Computing a sum modulo 2 (cumulative xor) of n boolean inputs requires an exponential number of elements if you only have or, not and and gates to work with. (regardless of circuit depth, actually).
Are you sure it's exponential ?
If you look at binary functions (ie. boolean circuits) any such function can be represented by a single layer function whose size is linear in the number of gates of the original function (I think it's 3 or 4 variables per gate) by converting to conjunctive normal form.
Of course it's not obvious that a similar scaling exists for non-binary functions but I'd be a bit surprised if increasing depth led to an exponential gain in representational efficiency.