Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-068 | 3rd May 2013 03:07

Lower Bounds for Depth 4 Homogenous Circuits with Bounded Top Fanin

RSS-Feed




TR13-068
Authors: Mrinal Kumar, Shubhangi Saraf
Publication: 3rd May 2013 03:40
Downloads: 1148
Keywords: 


Abstract:

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$.



ISSN 1433-8092 | Imprint