Document

**Published in:** LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

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.

Stasys Jukna and Andrzej Lingas. Lower Bounds for DeMorgan Circuits of Bounded Negation Width. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jukna_et_al:LIPIcs.STACS.2019.41, author = {Jukna, Stasys and Lingas, Andrzej}, title = {{Lower Bounds for DeMorgan Circuits of Bounded Negation Width}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {41:1--41:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.41}, URN = {urn:nbn:de:0030-drops-102801}, doi = {10.4230/LIPIcs.STACS.2019.41}, annote = {Keywords: Boolean circuits, monotone circuits, lower bounds} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

We consider the power of single level circuits in the context of
graph complexity. We first prove that the single level conjecture
fails for fanin-$2$ circuits over the basis ${oplus,land,1}$.
This shows that the (surpisingly tight) phenomenon, established by
Mirwald and Schnorr (1992) for quadratic functions, has no analogon
for graphs. We then show that the single level conjecture fails for
unbounded fanin circuits over ${lor,land,1}$. This partially
answers the question of Pudl'ak, R"odl and Savick'y (1986). We
also prove that $Sigma_2
eq Pi_2$ in a restricted version of the
hierarhy of communication complexity classes introduced by Babai,
Frankl and Simon (1986). Further, we show that even depth-$2$
circuits are surprisingly powerful: every bipartite $n imes n$
graph of maximum degree $Delta$ can be represented by a monotone
CNF with $O(Deltalog n)$ clauses. We also discuss a relation
between graphs and $ACC$-circuits.

Stasys Jukna. Graphs and Circuits: Some Further Remarks. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{jukna:DagSemProc.06111.8, author = {Jukna, Stasys}, title = {{Graphs and Circuits: Some Further Remarks}}, booktitle = {Complexity of Boolean Functions}, pages = {1--16}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6111}, editor = {Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.8}, URN = {urn:nbn:de:0030-drops-6218}, doi = {10.4230/DagSemProc.06111.8}, annote = {Keywords: Graph complexity, single level conjecture, Sylvester graphs, communication complexity, ACC-circuits} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

It is known that, for every constant $kgeq 3$, the presence of a
$k$-clique (a complete subgraph on $k$ vertices) in an $n$-vertex
graph cannot be detected by a monotone boolean circuit using fewer
than $Omega((n/log n)^k)$ gates. We show that, for every constant
$k$, the presence of an $(n-k)$-clique in an $n$-vertex graph can be
detected by a monotone circuit using only $O(n^2log n)$ gates.
Moreover, if we allow unbounded fanin, then $O(log n)$ gates are
enough.

Alexander E. Andreev and Stasys Jukna. Very Large Cliques are Easy to Detect. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{andreev_et_al:DagSemProc.06111.22, author = {Andreev, Alexander E. and Jukna, Stasys}, title = {{Very Large Cliques are Easy to Detect}}, booktitle = {Complexity of Boolean Functions}, pages = {1--7}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6111}, editor = {Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.22}, URN = {urn:nbn:de:0030-drops-6092}, doi = {10.4230/DagSemProc.06111.22}, annote = {Keywords: Clique function, monotone circuits, perfect hashing} }