An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin.
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi · Electronic colloquium on computational complexity · 2012
Agrawal and Vinay [AV08] have recently shown that an exponential lower bound for depth four homogeneous circuits with bottom layer of × 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 the permanent and determinant via homogeneous depth four circuits with bounded bottom fanin. We show here that any homogeneous depth four arithmetic circuit with bounded bottom fanin computing the permanent (or the determinant) must be of exponential size.