Advanced

Lower bounds for Demorgan circuits of bounded negation width

Jukna, Stasys and Lingas, Andrzej LU (2019) In Leibniz International Proceedings in Informatics, LIPIcs 126.
Abstract

We consider Boolean circuits over {∨, ∧, ¬} with negations applied only to input variables. To measure the “amount of negation” in such circuits, we introduce the concept of their “negation width.” In particular, a circuit computing a monotone Boolean function f(x1, . . ., xn) has negation width w if no nonzero term produced (purely syntactically) by the circuit contains more than w distinct negated variables. Circuits of negation width w = 0 are equivalent to monotone Boolean circuits, while those of negation width w = n have no restrictions. Our motivation is that already circuits of moderate negation width w = n for an arbitrarily small constant > 0 can be even exponentially stronger than monotone circuits. We show that the size... (More)

We consider Boolean circuits over {∨, ∧, ¬} with negations applied only to input variables. To measure the “amount of negation” in such circuits, we introduce the concept of their “negation width.” In particular, a circuit computing a monotone Boolean function f(x1, . . ., xn) has negation width w if no nonzero term produced (purely syntactically) by the circuit contains more than w distinct negated variables. Circuits of negation width w = 0 are equivalent to monotone Boolean circuits, while those of negation width w = n have no restrictions. Our motivation is that already circuits of moderate negation width w = n for an arbitrarily small constant > 0 can be even exponentially stronger than monotone circuits. We show that the size of any circuit of negation width w computing f is roughly at least the minimum size of a monotone circuit computing f divided by K = min{wm, mw}, where m is the maximum length of a prime implicant of f. We also show that the depth of any circuit of negation width w computing f is roughly at least the minimum depth of a monotone circuit computing f minus log K. Finally, we show that formulas of bounded negation width can be balanced to achieve a logarithmic (in their size) depth without increasing their negation width.

(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 circuits, Lower bounds, Monotone circuits
host publication
36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019
series title
Leibniz International Proceedings in Informatics, LIPIcs
editor
Niedermeier, Rolf ; Paul, Christophe ; and
volume
126
article number
41
publisher
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
external identifiers
  • scopus:85074945391
ISSN
1868-8969
ISBN
9783959771009
DOI
10.4230/LIPIcs.STACS.2019.41
language
English
LU publication?
yes
id
1b3cb4eb-17e8-499b-995a-8c749f2c9732
date added to LUP
2019-12-02 14:20:20
date last changed
2019-12-03 02:21:17
@inproceedings{1b3cb4eb-17e8-499b-995a-8c749f2c9732,
  abstract     = {<p>We consider Boolean circuits over {∨, ∧, ¬} with negations applied only to input variables. To measure the “amount of negation” in such circuits, we introduce the concept of their “negation width.” In particular, a circuit computing a monotone Boolean function f(x1, . . ., xn) has negation width w if no nonzero term produced (purely syntactically) by the circuit contains more than w distinct negated variables. Circuits of negation width w = 0 are equivalent to monotone Boolean circuits, while those of negation width w = n have no restrictions. Our motivation is that already circuits of moderate negation width w = n for an arbitrarily small constant &gt; 0 can be even exponentially stronger than monotone circuits. We show that the size of any circuit of negation width w computing f is roughly at least the minimum size of a monotone circuit computing f divided by K = min{w<sup>m</sup>, m<sup>w</sup>}, where m is the maximum length of a prime implicant of f. We also show that the depth of any circuit of negation width w computing f is roughly at least the minimum depth of a monotone circuit computing f minus log K. Finally, we show that formulas of bounded negation width can be balanced to achieve a logarithmic (in their size) depth without increasing their negation width.</p>},
  author       = {Jukna, Stasys and Lingas, Andrzej},
  booktitle    = {36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019},
  editor       = {Niedermeier, Rolf and Paul, Christophe},
  isbn         = {9783959771009},
  issn         = {1868-8969},
  language     = {eng},
  publisher    = {Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing},
  series       = {Leibniz International Proceedings in Informatics, LIPIcs},
  title        = {Lower bounds for Demorgan circuits of bounded negation width},
  url          = {http://dx.doi.org/10.4230/LIPIcs.STACS.2019.41},
  doi          = {10.4230/LIPIcs.STACS.2019.41},
  volume       = {126},
  year         = {2019},
}