__
Revision #1 to TR22-094 | 7th July 2022 22:46
__
#### Notes on Monotone Read-k Circuits

**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.

__
TR22-094 | 3rd July 2022 20:59
__

#### Notes on Monotone Read-k Circuits

**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.