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 #2 to TR22-094 | 26th December 2022 19:47

Notes on Boolean Read-k and Multilinear Circuits

RSS-Feed




Revision #2
Authors: Stasys Jukna
Accepted on: 26th December 2022 19:47
Downloads: 138
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 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.



Changes to previous version:

Added Corollary 1, Section 6.2, Facts 1 and 3 to 5, Remarks 4 and 5.


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

Notes on Monotone Read-k Circuits





Revision #1
Authors: Stasys Jukna
Accepted on: 7th July 2022 22:46
Downloads: 194
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: 308
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