Advanced

Towards an almost quadratic lower bound on the monotone circuit complexity of the Boolean convolution

Lingas, Andrzej LU (2017) 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 In Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings 10185 LNCS. p.401-411
Abstract

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 distinct subsets of input variables induced by monoms at the output gates. We show that any monotone Boolean circuit of log n-bounded and-depth computing a Boolean semi-disjoint form with 2n input variables and q prime impli-cants has Ω(q/n2) size. As a corollary, we obtain the Ω(n2−2) lower bound on the size of any monotone... (More)

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 distinct subsets of input variables induced by monoms at the output gates. We show that any monotone Boolean circuit of log n-bounded and-depth computing a Boolean semi-disjoint form with 2n input variables and q prime impli-cants has Ω(q/n2) size. As a corollary, we obtain the Ω(n2−2) lower bound on the size of any monotone Boolean circuit of so bounded and-depth computing the n-dimensional Boolean vector convolution. Fur-thermore, we show that any monotone Boolean circuit of 2n -bounded monom number, computing a Boolean semi-disjoint form on 2n variables, where each variable occurs in p prime implicants, has Ω(n1−2 p) size. As a corollary, we obtain the Ω(n2−2) lower bound on the size of any monotone Boolean circuit of 2n -bounded monom number computing the n-dimensional Boolean vector convolution. Finally, we demonstrate that in any monotone Boolean circuit for a semi-disjoint bilinear form with q prime implicants that has size substantially smaller than q, the major-ity 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 n-dimensional Boolean vec-tor convolution of size o(n2−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)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Boolean vector convolution, Monotone Boolean circuit complexity, Semi-disjoint bilinear form
in
Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings
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/978-3-319-55911-7_29
language
English
LU publication?
yes
id
6b4d1a80-df13-49e4-9f04-dd9abb75513e
date added to LUP
2017-05-23 09:23:30
date last changed
2017-06-08 13:34:20
@inproceedings{6b4d1a80-df13-49e4-9f04-dd9abb75513e,
  abstract     = {<p>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 distinct subsets of input variables induced by monoms at the output gates. We show that any monotone Boolean circuit of log n-bounded and-depth computing a Boolean semi-disjoint form with 2n input variables and q prime impli-cants 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 and-depth computing the n-dimensional Boolean vector convolution. Fur-thermore, we show that any monotone Boolean circuit of 2<sup>n</sup> -bounded monom number, computing a Boolean semi-disjoint 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 n-dimensional Boolean vector convolution. Finally, we demonstrate that in any monotone Boolean circuit for a semi-disjoint bilinear form with q prime implicants that has size substantially smaller than q, the major-ity 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 n-dimensional Boolean vec-tor 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    = {Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings},
  isbn         = {9783319559100},
  issn         = {16113349},
  keyword      = {Boolean vector convolution,Monotone Boolean circuit complexity,Semi-disjoint bilinear form},
  language     = {eng},
  pages        = {401--411},
  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/978-3-319-55911-7_29},
  volume       = {10185 LNCS},
  year         = {2017},
}