Lower bounds for Demorgan circuits of bounded negation width

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

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 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.

Details

Authors
Organisations
External organisations
  • Vilnius University
  • Goethe University
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computer Science

Keywords

  • Boolean circuits, Lower bounds, Monotone circuits
Original languageEnglish
Title of host publication36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019
EditorsRolf Niedermeier, Christophe Paul
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771009
Publication statusPublished - 2019
Publication categoryResearch
Peer-reviewedYes
Event36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019 - Berlin, Germany
Duration: 2019 Mar 132019 Mar 16

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume126
ISSN (Print)1868-8969

Conference

Conference36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019
CountryGermany
CityBerlin
Period2019/03/132019/03/16