Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR22-094 | 7th July 2022 22:46

Notes on Monotone Read-k Circuits

RSS-Feed




Revision #1
Authors: Stasys Jukna
Accepted on: 7th July 2022 22:46
Downloads: 30
Keywords: 


Abstract:

A monotone Boolean circuit computing a Boolean function $f$ is a read-$k$ circuit if the polynomial produced (purely syntactically) by the arithmetic $(+,\times)$ version of the circuit has the property that for every prime implicant of $f$, the polynomial contains a monomial with the same set of variables, each appearing with degree $\leq k$. Every monotone circuit is a read-$k$ circuit for some~$k$.

We show that monotone read-1 circuits have the same power as tropical $(\min,+)$ circuits solving $0/1$ optimization, and the same power as monotone arithmetic $(+,\times)$ circuits computing multilinear homogeneous polynomials.
We also show that monotone read-1 circuits are not weaker than multilinear non-monotone $(\lor,\land,\neg)$ circuits. Finally, we show that already read-2 monotone circuits can be exponentially smaller than read-1 monotone circuits.



Changes to previous version:

The last part (multilinear circuits) is substantially shortened and simplified. The presentation of the rest is also improved.


Paper:

TR22-094 | 3rd July 2022 20:59

Notes on Monotone Read-k Circuits





TR22-094
Authors: Stasys Jukna
Publication: 3rd July 2022 21:00
Downloads: 126
Keywords: 


Abstract:

A monotone Boolean $(\lor,\land)$ circuit $F$ computing a Boolean function $f$ is a read-$k$ circuit if the polynomial produced (purely syntactically) by the arithmetic $(+,\times)$ version of $F$ has the property that for every prime implicant of $f$, the polynomial contains a monomial with the same set of variables, each appearing with degree $\leq k$. Every monotone $(\lor,\land)$ circuit is a read-$k$ circuit for some $k$.

We first show that already read-1 circuits are interesting in the context of dynamic programming: tropical $(\min,+)$ circuits solving $0/1$ optimization problems have the same power as Boolean read-1 circuits, and that
monotone read-1 $(\lor,\land)$ circuits computing homogeneous Boolean functions are not stronger than monotone arithmetic circuits. Then we show that already read-2 circuits can be exponentially smaller than read-1 circuits. Finally, we show that so-called (semantically) multilinear DeMorgan $(\lor,\land,\neg)$ circuits computing monotone Boolean functions are not stronger than monotone read-1 circuits.



ISSN 1433-8092 | Imprint