Agrawal-Vinay (FOCS 2008) and Koiran (TCS 2012) have recently shown that an
exp(√(n) * log^{2} n)) lower bound for depth four homogeneous circuits
computing the permanent with bottom layer of gates having fanin bounded by √(n)
translates to super-polynomial lower bound for a general arithmetic circuits
computing the permanent. Motivated by this, we examine the complexity of
computing the permanent and determinant via such homogeneous depth four circuits
with bounded bottom fanin.

We show here that any homogeneous depth four arithmetic circuit with bottom fanin bounded by √(n) computing the permanent (or the determinant) must be of size exp(√(n)) .

}, author = {Ankit Gupta and Pritish Kamath and Neeraj Kayal and Ramprasad Saptharishi}, booktitle = {Conference on Computational Complexity}, month = {June}, publisher = {IEEE}, title = {Approaching the chasm at depth four}, url = {http://research.microsoft.com/apps/pubs/default.aspx?id=189020}, year = {2013}, }