7 ms·
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
by tgflynn 14y ago
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.
- bravura 14y agoI 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 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)."
- tgflynn 14y agoI 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.
- beagle3 14y agoComputing 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).