Super-polynomial lower bounds for depth four homogeneous arithmetic formulas
- Neeraj Kayal ,
- Nutan Limaye ,
- Chandan Saha ,
- Srikanth Srinivasan
Symposium on Theory of Computing (STOC) |
Published by ACM - Association for Computing Machinery
We show that any depth four homogeneous arithmetic formula computing the Iterated Matrix Multiplication polynomial IMMn, d — the (1, 1)-th entry of the product of d generic n-by-n matrices — has size at least nlog n, if d >= log2 n .
© ACM. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version can be found at http://dl.acm.org.