Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth
(2020) In Theoretical Computer Science 820. p.17-25- Abstract
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 ϵlogn conjunction-depth computing the n-dimensional Boolean vector convolution has Ω(n2−4ϵ) and-gates. For Boolean matrix product, we derive even a stronger lower-bound trade-off. Instead of conjunction-depth we use the... (More)
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 ϵlogn conjunction-depth computing the n-dimensional Boolean vector convolution has Ω(n2−4ϵ) 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 ϵlogn negation-dependent conjunction-depth computes the n×n Boolean matrix product then the circuit has Ω(n3−2ϵ) 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.
(Less)
- author
- Lingas, Andrzej LU
- organization
- publishing date
- 2020-06-08
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Boolean circuit complexity, Boolean circuits, Boolean matrix product, Boolean vector convolution, Semi-disjoint bilinear form
- in
- Theoretical Computer Science
- volume
- 820
- pages
- 9 pages
- publisher
- Elsevier
- external identifiers
-
- scopus:85082121403
- ISSN
- 0304-3975
- DOI
- 10.1016/j.tcs.2020.03.005
- language
- English
- LU publication?
- yes
- id
- d71efbdd-2b08-4517-8877-8ded765d0abd
- date added to LUP
- 2020-04-08 09:43:51
- date last changed
- 2022-04-18 21:50:58
@article{d71efbdd-2b08-4517-8877-8ded765d0abd, abstract = {{<p>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 ϵlogn conjunction-depth computing the n-dimensional Boolean vector convolution has Ω(n<sup>2−4ϵ</sup>) 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 ϵlogn negation-dependent conjunction-depth computes the n×n Boolean matrix product then the circuit has Ω(n<sup>3−2ϵ</sup>) 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.</p>}}, author = {{Lingas, Andrzej}}, issn = {{0304-3975}}, keywords = {{Boolean circuit complexity; Boolean circuits; Boolean matrix product; Boolean vector convolution; Semi-disjoint bilinear form}}, language = {{eng}}, month = {{06}}, pages = {{17--25}}, publisher = {{Elsevier}}, series = {{Theoretical Computer Science}}, title = {{Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth}}, url = {{http://dx.doi.org/10.1016/j.tcs.2020.03.005}}, doi = {{10.1016/j.tcs.2020.03.005}}, volume = {{820}}, year = {{2020}}, }