Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-085 | 8th June 2022 14:36

A Note on Lower Bounds for Monotone Multilinear Boolean Circuits



A monotone Boolean circuit is a restriction of a Boolean circuit
allowing for the use of disjunctions, conjunctions, the Boolean
constants, and the input variables. A monotone Boolean circuit is
multilinear if for any AND gate the two input functions have no
variable in common. We show that the known lower bounds on the size
of monotone arithmetic circuits for multivariate polynomials that
are sums of monomials consisting of $k$ distinct variables yield the
analogous lower bounds divided by $O(k^2)$ on the size of monotone
multilinear Boolean circuits computing the Boolean functions
represented by the corresponding multivariate Boolean polynomials.

ISSN 1433-8092 | Imprint