Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR08-019 | 20th March 2008 00:00

Entropy of operators or why matrix multiplication is hard for depth-two circuits

RSS-Feed




Revision #1
Authors: Stasys Jukna
Accepted on: 20th March 2008 00:00
Downloads: 3056
Keywords: 


Abstract:


Paper:

TR08-019 | 6th March 2008 00:00

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





TR08-019
Authors: Stasys Jukna
Publication: 6th March 2008 13:10
Downloads: 1983
Keywords: 


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.



ISSN 1433-8092 | Imprint