Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth

Lingas, Andrzej LU (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 ϵlog⁡n 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 ϵlog⁡n 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 ϵlog⁡n 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)
Please use this url to cite or link to this publication:
author
organization
publishing date
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 ϵlog⁡n 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 ϵlog⁡n 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}},
}