Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Lower bounds for Demorgan circuits of bounded negation width

Jukna, Stasys and Lingas, Andrzej LU (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)
Please use this url to cite or link to this publication:
author
and
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 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 &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}},
  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}},
}