Lower Bounds for Depth 4 Homogenous Circuits with Bounded Top Fanin.
Mrinal Kumar, Shubhangi Saraf · Electronic colloquium on computational complexity · 2013
We study the class of homogenous ΣΠΣΠ(r) circuits, which are depth 4 homogenous circuits with top fanin bounded by r. We show that any homogenous ΣΠΣΠ(r) circuit computing the permanent of an n× n matrix must have size at least exp ( n ) . 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×n matrix must have size at least exp (Ω(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 D = D1, D2, . . . , Dk of nonnegative integers such that ∑ Di = n, we also study the class of homogenous ΣΠDΣΠ circuits, which are homogenous circuits where each Π gate at the second layer (from the the top) is restricted to having its inputs be polynomials whose sequence of degrees is precisely D. We show that for every degree sequence D, any ΣΠDΣΠ circuit computing the permanent of an n× n matrix must have size at least exp (n ), for some fixed absolute constant independent of D. ∗Department of Computer Science, Rutgers University. Email: [email protected]. †Department of Computer Science and Department of Mathematics, Rutgers University. Email: [email protected].