Lower Bounds for Monotone q-Multilinear Boolean Circuits

A monotone Boolean circuit is composed of OR gates, AND gates and input gates corresponding to the input variables and the Boolean constants. It is multilinear if for any AND gate the two input functions have no variable in common. We consider a generalization of monotone multilinear Boolean circuits to include monotone q-multilinear Boolean circuits. Roughly, a sufficient condition for the q-multilinearity is that in the formal Boolean polynomials at the output gates of the circuit no variable has degree larger than q. First, we study a relationship between q-multilinearity and the conjunction depth of a monotone Boolean circuit, i.e., the maximum number of AND gates on a path from an input gate to an output gate. As a corollary, we obtain a trade-off between the lower bounds on the size of monotone q-multilinear Boolean circuits for semi-disjoint bilinear forms and the parameter q. Next, we study the complexity of the monotone Boolean function Isol(k,n) verifying if a k-dimensional matrix has at least one 1 in each line (e.g., each row and column when k = 2) in terms of monotone k-multilinear Boolean circuits. We show that the function admits Pi(2) monotone k-multilinear circuits of O(n(k)) size. On the other hand, we demonstrate that any Pi(2) monotone Boolean circuit for Isol(k,n) is at least k-multilinear. Also, we show under an additional assumption that any Sigma(3) monotone Boolean circuit for Isol(k,n) is not (k - 1)-multilinear or it has an exponential in n size.