Towards an almost quadratic lower bound on the monotone circuit complexity of the Boolean convolution
(2017) 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10185 LNCS. p.401411 Abstract
We study the monotone circuit complexity of the so called semidisjoint bilinear forms over the Boolean semiring, in particular the ndimensional Boolean vector convolution. Besides the size of a monotone Boolean circuit, we consider also the anddepth of the circuit, i.e., the maximum number of andgates on a path to an output gate, and the monom number of the circuit which is the number of distinct subsets of input variables induced by monoms at the output gates. We show that any monotone Boolean circuit of log nbounded anddepth computing a Boolean semidisjoint form with 2n input variables and q prime implicants has Ω(q/n^{2}) size. As a corollary, we obtain the Ω(n^{2−2}) lower bound on the size of any monotone... (More)
We study the monotone circuit complexity of the so called semidisjoint bilinear forms over the Boolean semiring, in particular the ndimensional Boolean vector convolution. Besides the size of a monotone Boolean circuit, we consider also the anddepth of the circuit, i.e., the maximum number of andgates on a path to an output gate, and the monom number of the circuit which is the number of distinct subsets of input variables induced by monoms at the output gates. We show that any monotone Boolean circuit of log nbounded anddepth computing a Boolean semidisjoint form with 2n input variables and q prime implicants has Ω(q/n^{2}) size. As a corollary, we obtain the Ω(n^{2−2}) lower bound on the size of any monotone Boolean circuit of so bounded anddepth computing the ndimensional Boolean vector convolution. Furthermore, we show that any monotone Boolean circuit of 2^{n} bounded monom number, computing a Boolean semidisjoint form on 2n variables, where each variable occurs in p prime implicants, has Ω(n^{1−2} p) size. As a corollary, we obtain the Ω(n^{2−2}) lower bound on the size of any monotone Boolean circuit of 2^{n} bounded monom number computing the ndimensional Boolean vector convolution. Finally, we demonstrate that in any monotone Boolean circuit for a semidisjoint bilinear form with q prime implicants that has size substantially smaller than q, the majority of the terms at the output gates representing prime implicants have to have very large length (i.e., the number of variable occurrences). In particular, in any monotone circuit for the ndimensional Boolean vector convolution of size o(n^{2−4}/log n) almost all prime implicants of the convolution have to be represented by terms at the circuit output gates of length at least n.
(Less)
 author
 Lingas, Andrzej ^{LU}
 organization
 publishing date
 2017
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 Boolean vector convolution, Monotone Boolean circuit complexity, Semidisjoint bilinear form
 in
 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
 volume
 10185 LNCS
 pages
 11 pages
 publisher
 Springer Verlag
 conference name
 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017
 external identifiers

 scopus:85018413941
 ISSN
 16113349
 03029743
 ISBN
 9783319559100
 DOI
 10.1007/9783319559117_29
 language
 English
 LU publication?
 yes
 id
 6b4d1a80df1349e49f04dd9abb75513e
 date added to LUP
 20170523 09:23:30
 date last changed
 20180107 12:04:44
@inproceedings{6b4d1a80df1349e49f04dd9abb75513e, abstract = {<p>We study the monotone circuit complexity of the so called semidisjoint bilinear forms over the Boolean semiring, in particular the ndimensional Boolean vector convolution. Besides the size of a monotone Boolean circuit, we consider also the anddepth of the circuit, i.e., the maximum number of andgates on a path to an output gate, and the monom number of the circuit which is the number of distinct subsets of input variables induced by monoms at the output gates. We show that any monotone Boolean circuit of log nbounded anddepth computing a Boolean semidisjoint form with 2n input variables and q prime implicants has Ω(q/n<sup>2</sup>) size. As a corollary, we obtain the Ω(n<sup>2−2</sup>) lower bound on the size of any monotone Boolean circuit of so bounded anddepth computing the ndimensional Boolean vector convolution. Furthermore, we show that any monotone Boolean circuit of 2<sup>n</sup> bounded monom number, computing a Boolean semidisjoint form on 2n variables, where each variable occurs in p prime implicants, has Ω(n<sup>1−2</sup> p) size. As a corollary, we obtain the Ω(n<sup>2−2</sup>) lower bound on the size of any monotone Boolean circuit of 2<sup>n</sup> bounded monom number computing the ndimensional Boolean vector convolution. Finally, we demonstrate that in any monotone Boolean circuit for a semidisjoint bilinear form with q prime implicants that has size substantially smaller than q, the majority of the terms at the output gates representing prime implicants have to have very large length (i.e., the number of variable occurrences). In particular, in any monotone circuit for the ndimensional Boolean vector convolution of size o(n<sup>2−4</sup>/log n) almost all prime implicants of the convolution have to be represented by terms at the circuit output gates of length at least n.</p>}, author = {Lingas, Andrzej}, booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}, isbn = {9783319559100}, issn = {16113349}, keyword = {Boolean vector convolution,Monotone Boolean circuit complexity,Semidisjoint bilinear form}, language = {eng}, pages = {401411}, publisher = {Springer Verlag}, title = {Towards an almost quadratic lower bound on the monotone circuit complexity of the Boolean convolution}, url = {http://dx.doi.org/10.1007/9783319559117_29}, volume = {10185 LNCS}, year = {2017}, }