Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PARTIAL DERIVATIVE:
Reports tagged with partial derivative:
TR12-098 | 3rd August 2012
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

#### An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin

Revisions: 3

Agrawal and Vinay (FOCS 2008) have recently shown that an exponential lower bound for depth four homogeneous circuits with bottom layer of $\times$ gates having sublinear fanin translates to an exponential lower bound for a general arithmetic circuit computing the permanent. Motivated by this, we examine the complexity of computing ... more >>>

ISSN 1433-8092 | Imprint