Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-108 | 1st June 2018 22:35

Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth


Authors: Andrzej Lingas
Publication: 2nd June 2018 21:56
Downloads: 68


We consider normalized Boolean circuits that use binary operations of disjunction and conjunction, and unary negation, with the restriction that negation can be only applied to input variables. We derive a lower bound trade-off between the size of normalized Boolean circuits computing Boolean semi-disjoint bilinear forms and their conjunction-depth (i.e., the maximum number of and-gates on a directed path to an output gate). In particular, we show that any normalized Boolean circuit of at most $\epsilon \log n$ conjunction-depth computing the $n$-dimensional Boolean vector convolution has $\Omega(n^{2-4\epsilon})$ and-gates.For Boolean matrix product, we derive even a stronger lower-bound trade-off. Instead of conjunction-depth we use the negation-dependent conjunction-depth, where one counts only and-gates whose each direct predecessor has a (not necessarily direct) predecessor representing a negated input variable. We show that if a normalized Boolean circuit of at most $\epsilon \log n$ negation-dependent conjunction-depth computes the $n\times n$ Boolean matrix product then the circuit has $\Omega(n^{3-2\epsilon})$ and-gates. We complete our lower-bound trade-offs for the Boolean convolution and matrix product with upper-bound trade-offs of similar form yielded by the known fast algebraic algorithms.

ISSN 1433-8092 | Imprint