__
TR08-019 | 6th March 2008 00:00
__

#### Entropy of operators or why matrix multiplication is hard for small depth circuits

**Abstract:**
In this note 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 is as the logarithm of the maximum number of vectors distinguishable by at least one special subfunction of f. Then we prove that every depth-2 circuit for f requires at least entropy(f) wires. This generalizes and substantially simplifies the argument used by Cherukhin in 2005 to derive the highest known lower bound n^{3/2} for the operator of cyclic convolutions. We then show that the multiplication of two n^{1/2} by n^{1/2} matrices over any finite field has entropy at least n^{3/2}. All proofs are elementary.