Abstract
We consider unbounded fanin depth-2 circuits with arbitrary boolean functions as gates. We define the entropy of an operator f:{0,1}^n --> {0,1}^m as the logarithm of the maximum number of vectors distinguishable by at least one special subfunction of f.
Our main result is that every depth-2 circuit for f requires at least entropy(f) wires. This gives an information-theoretic explanation of why some operators require many wires. We use this to prove a tight estimate n^3 of the smallest number of wires in any depth-2 circuit computing the product of two n by n matrices over any finite field. Previously known lower bound for this operator was n^2\log n.