On the Power of Homogeneous Depth 4 Arithmetic Circuits
On the Power of Homogeneous Depth 4 Arithmetic Circuits
We prove exponential lower bounds on the size of homogeneous depth 4 arithmetic circuits computing an explicit polynomial in $VP$. Our results hold for the iterated matrix multiplication polynomial---in particular we show that any homogeneous depth 4 circuit computing the (1,1) entry in the product of $n$ generic matrices of …