Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HOMOGENEOUS DEPTH 4 ARITHMETIC CIRCUITS:
Reports tagged with Homogeneous depth 4 arithmetic circuits:
TR14-045 | 7th April 2014
Mrinal Kumar, Shubhangi Saraf

#### On the power of homogeneous depth 4 arithmetic circuits

Revisions: 2

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 Multiplication} polynomial - in particular we show that any homogeneous depth 4 circuit computing the $(1,1)$ entry in the product of $n$ ... more >>>

ISSN 1433-8092 | Imprint