| Title |
Lower bounds for DeMorgan circuits of bounded negation width / |
| Authors |
Jukna, Stasys ; Lingas, Andrej |
| DOI |
10.4230/LIPIcs.STACS.2019.41 |
| ISBN |
9783959771009 |
| Full Text |
|
| Is Part of |
36th International symposium on theoretical aspects of computer science (STACS 2019), March 13-16, 2019, Berlin, Germany / Editors: Rolf Niedermeier and Christophe Paul.. Wadern : Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2019. art. no. 41, p. [1-17].. ISBN 9783959771009 |
| Keywords [eng] |
Boolean circuits ; monotone circuits ; lower bounds ; negation |
| Abstract [eng] |
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. |
| Published |
Wadern : Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2019 |
| Type |
Conference paper |
| Language |
English |
| Publication date |
2019 |
| CC license |
|
