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.

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

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.

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

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.