TR13-068 Authors: Mrinal Kumar, Shubhangi Saraf

Publication: 3rd May 2013 03:40

Downloads: 1871

Keywords:

We study the class of homogenous $\Sigma\Pi\Sigma\Pi(r)$ circuits, which are depth 4 homogenous circuits with top fanin bounded by $r$. We show that any homogenous $\Sigma\Pi\Sigma\Pi(r)$ circuit computing the permanent of an $n\times n$ matrix must have size at least $\exp\left(n^{\Omega(1/r)}\right)$.

In a recent result, Gupta, Kamath, Kayal and Saptharishi [6] showed that any homogenous depth 4 circuit with bottom fanin bounded by $t$ which computes the permanent of an $n\times n$ matrix must have size at least $\exp{(\Omega(n/t))}$. Our work builds upon the results of [6], and explores the limits of computation of depth four homogenous circuits when the restriction for the bottom fanin is removed.

For any sequence $\mathcal D = D_1, D_2, \ldots, D_k$ of nonnegative integers such that $\sum D_i = n$, we also study the class of homogenous $\Sigma\Pi^{\mathcal D}\Sigma\Pi$ circuits, which are homogenous circuits where each $\Pi$ gate at the second layer (from the the top) is restricted to having its inputs be polynomials whose sequence of degrees is precisely $\mathcal D$. We show that for every degree sequence $\mathcal D$, any $\Sigma\Pi^{\mathcal D}\Sigma\Pi$ circuit computing the permanent of an $n\times n$ matrix must have size at least $\exp\left(n^{\epsilon}\right)$, for some fixed absolute constant $\epsilon$ independent of $\mathcal D$.