Lower bounds for Demorgan circuits of bounded negation width
(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{w^{m}, m^{w}}, 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)
 author
 Jukna, Stasys and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2019
 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 LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing
 external identifiers

 scopus:85074945391
 ISSN
 18688969
 ISBN
 9783959771009
 DOI
 10.4230/LIPIcs.STACS.2019.41
 language
 English
 LU publication?
 yes
 id
 1b3cb4eb17e8499b995a8c749f2c9732
 date added to LUP
 20191202 14:20:20
 date last changed
 20191203 02:21:17
@inproceedings{1b3cb4eb17e8499b995a8c749f2c9732, 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 > 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 = {18688969}, language = {eng}, publisher = {Schloss Dagstuhl LeibnizZentrum 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}, }