Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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