Lower bounds for Demorgan circuits of bounded negation width
(2019) 36th International Symposium on Theoretical Aspects of Computer Science, STACS 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)
- 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 and Paul, Christophe
- volume
- 126
- article number
- 41
- publisher
- Schloss Dagstuhl - Leibniz-Zentrum für Informatik
- conference name
- 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019
- conference location
- Berlin, Germany
- conference dates
- 2019-03-13 - 2019-03-16
- 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
- 2022-04-18 19:22:53
@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 > 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}}, keywords = {{Boolean circuits; Lower bounds; Monotone circuits}}, language = {{eng}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}}, 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}}, }