2026-10-15T12:18:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10280 2024-03-06T09:45:42Z ddc:004 open_access

Lower Bounds for DeMorgan Circuits of Bounded Negation Width Jukna, Stasys Lingas, Andrzej Boolean circuits monotone circuits lower bounds We consider Boolean circuits over {or, and, neg} 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(x_1,...,x_n) 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^{epsilon} for an arbitrarily small constant epsilon>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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stasys Jukna and Andrzej Lingas 2019 Is Part Of LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2019.41 urn:nbn:de:0030-drops-102801 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.41 eng https://creativecommons.org/licenses/by/3.0/legalcode