ECCC-Report TR22-094https://eccc.weizmann.ac.il/report/2022/094Comments and Revisions published for TR22-094en-usMon, 26 Dec 2022 19:47:01 +0200
Revision 2
| Notes on Boolean Read-k and Multilinear Circuits |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2022/094#revision2A 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 show that monotone read-1 circuits have the same power as: tropical $(\min,+)$ circuits solving $0/1$ minimization problems, monotone arithmetic $(+,\times)$ circuits computing multilinear homogeneous polynomials, as well as non-monotone $(\lor,\land,\neg)$ circuits computing monotone homogeneous Boolean functions. Finally, we show that already monotone read-2 circuits can be exponentially smaller than monotone read-1 circuits.
Mon, 26 Dec 2022 19:47:01 +0200https://eccc.weizmann.ac.il/report/2022/094#revision2
Revision 1
| Notes on Monotone Read-k Circuits |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2022/094#revision1A 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.Thu, 07 Jul 2022 22:46:09 +0300https://eccc.weizmann.ac.il/report/2022/094#revision1
Paper TR22-094
| Notes on Monotone Read-k Circuits |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2022/094A 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.Sun, 03 Jul 2022 21:00:53 +0300https://eccc.weizmann.ac.il/report/2022/094