On the power of homogeneous depth 4 arithmetic circuits

Mrinal Kumar, Shubhangi Saraf

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 {\it Iterated Matrix Mul…