ECCC-Report TR18-108https://eccc.weizmann.ac.il/report/2018/108Comments and Revisions published for TR18-108en-usSat, 02 Jun 2018 21:56:05 +0300
Paper TR18-108
| Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth |
Andrzej Lingas
https://eccc.weizmann.ac.il/report/2018/108We 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.Sat, 02 Jun 2018 21:56:05 +0300https://eccc.weizmann.ac.il/report/2018/108