Notes on Boolean Read-k and Multilinear Circuits
S. Jukna
Abstract
A monotone Boolean $(\lor,\land)$ circuit computing
a monotone 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 at most k. Every monotone circuit is a read-k circuit
for some k.
We show that already read-1 $(\lor,\land)$ circuits are not weaker than
monotone arithmetic constant-free $(+,\times)$ circuits computing
multilinear polynomials, are not weaker than non-monotone
multilinear $(\lor,\land,\neg)$ circuits computing monotone
Boolean functions, and have the same power as tropical $(\min,+)$ circuits solving $0/1$ minimization problems.
Finally, we show that read-2 $(\lor,\land)$ circuits can be exponentially smaller than read-1 $(\lor,\land)$ circuits.
Paper