Entropy of operators or why matrix multiplication is hard for small depth circuits.
Stasys P. Jukna · Electronic colloquium on computational complexity · 2008
We consider unbounded fanin depth-2 circuits with arbitrary boolean functions as gates. The entropy of an operator f : {0, 1}n → {0, 1}m is defined as the logarithm of the maximum number of vectors distinguishable by at least one special subfunction of f . 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) for the operator of cyclic convolutions. We then show that the multiplication of two n by n matrices over any finite field has entropy Ω(n).