Towards an almost quadratic lower bound on the monotone circuit complexity of the Boolean convolution
We study the monotone circuit complexity of the so called semi-disjoint bilinear forms over the Boolean semi-ring, in particular the n-dimensional Boolean vector convolution. Besides the size of a monotone Boolean circuit, we consider also the and-depth of the circuit, i.e., the maximum number of and-gates on a path to an output gate, and the monom number of the circuit which is the number of dist
