# Notes on Boolean Read-k and Multilinear Circuits

Stasys Jukna<EMAIL_ADDRESS>[

###### 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 at
least one monomial with the same set of variables, each appearing with degree
$\leqslant 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.

###### keywords:

Arithmetic circuits , multilinear circuits , tropical circuits , lower bounds

###### MSC:

68Q17 , 94C11

††journal: Discrete Applied Mathematics

url]https://web.vu.lt/mif/s.jukna/

organization=Faculty of Mathematics and Computer Science, Vilnius University,
city=Vilnius, country=Lithuania

##  1 Introduction

Proving lower bounds on the size of arithmetic $(+,\times,-)$ circuits as well
as on the size of Boolean $(\lor,\land,\neg)$ circuits remains a notoriously
hard problem. Although the problem has received a great deal of attention for
decades, the best known lower bounds for arithmetic circuits computing
explicit multilinear $n$-variate polynomials with $0$-$1$ coefficients remain
barely super-linear bounds $\Omega(n\log n)$ proved by Baur and Strassen [3]
already in 1983. For Boolean circuits, known lower bounds are even not super-
linear. The first lower bound $2n$ was proved by Schnorr [37] in 1974, and
improved to $3n$ by Blum [4] in 1984; the best known lower bound $4.5n-o(n)$
was proved by Lachish and Raz [23] in 2001, and improved to $5n-o(n)$ by Iwama
and Morizumi [13]. In both circuit models (arithmetic and Boolean), super-
polynomial lower bounds are known only for restricted circuits such as
bounded-depth and monotone circuits. The books [5, 15, 48] and recent surveys
[6, 42] provide wide coverage of Boolean and arithmetic circuits.

This lack of proofs of strong lower bounds for unrestricted arithmetic and
Boolean circuits happens mainly because such circuits can use cancellations
$x-x=0$ in the arithmetic, and can use cancellations $x\land\overline{x}=0$ in
the Boolean case. Understanding the role of cancellations in arithmetic and
Boolean circuits remains the ultimate goal of circuit complexity.

Monotone arithmetic $(+,\times)$ circuits cannot use cancellations $x-x=0$,
while monotone Boolean $(\lor,\land)$ circuits cannot use cancellations
$x\land\overline{x}=0$. Still, the task of proving lower bounds even for
monotone _Boolean_ circuits turned out to be much more difficult than that for
monotone _arithmetic_ circuits. Although super-polynomial lower bounds on the
size of monotone arithmetic $(+,\times)$ circuits were known starting with the
notable paper by Schnorr [38] of 1976, it took a decade until such lower
bounds for monotone Boolean $(\lor,\land)$ circuits were proved by Razborov
[34, 35] in 1985; until then, the best known lower bound on the size of
monotone Boolean circuits was only $4n$ proved by Tiekenheinrich [45] in 1984.
This happens because Boolean circuits can use idempotence laws $x\lor x=x$ and
$x\land x=x$ as well as the absorption law $x\lor xy=x$, while arithmetic
circuits cannot use any of these laws. The current paper attempts to identify
a possible source for this discrepancy: the presence of multiplicative
idempotence and absorption in Boolean circuits.

It turned out that the absence of _additive_ idempotence $x\lor x=x$ in
arithmetic circuits (where $x+x\neq x$) is not a crucial issue: most lower
bounds (albeit not all, [49] being a nice exception) on the monotone
arithmetic $(+,\times)$ circuit complexity, including [8, 9, 14, 17, 33, 38,
41, 46, 47] were proved by only using the _structure_ of monomials and fully
ignoring actual values of their (nonzero) coefficients.

But the absence of _multiplicative_ idempotence $x\land x=x$ and absorption
$x\lor xy=x$ in the arithmetic world turned out to be crucial even in the case
of monotone circuits. The goal of this article is to show that already a _very
restricted_ use of multiplicative idempotence, in combination with absorption,
makes a big difference between Boolean and arithmetic circuits.

To fine grain the “degree” of multiplicative idempotence, and by analogy with
read-$k$ branching programs, we introduce (in Section 4) the so-called
“read-$k$” $(\lor,\land)$ circuits. Our goal is to show that already read-$1$
$(\lor,\land)$ circuits capture the power of three different types of
circuits: monotone _arithmetic_ $(+,\times)$ circuits, Boolean _multilinear_
DeMorgan $(\lor,\land,\neg)$ circuits, as well as _tropical_ 111 The adjective
“tropical” was coined by French mathematicians in honor of Imre Simon who
lived in Sao Paulo (south tropic). Tropical algebra and tropical geometry are
now intensively studied topics in mathematics. $(\min,+)$ circuits.

The latter model of (tropical) circuits is motivated by dynamic programming
(DP). Namely, many classical DP algorithms for minimization problems are
“pure” in that they only use $(\min,+)$ operations in their recursion
equations. Prominent examples of pure DP algorithms are the Bellman–Ford–Moore
shortest $s$-$t$ path algorithm, the Roy–Floyd–Warshall all-pairs shortest
paths algorithm, the Bellman–Held–Karp traveling salesman algorithm, the
Dreyfus–Levin–Wagner Steiner tree algorithm, and many others. On the other
hand, pure DP algorithms are just _special_ (recursively constructed) tropical
$(\min,+)$ circuits. Thus, any lower bound on the size of $(\min,+)$ circuits
is also a lower bound on the minimum number of operations that any pure DP
algorithm solving a given minimization problem must perform, be the designer
of an algorithm even omnipotent.

First lower bounds on the size of tropical circuits were proved already
decades ago, including Kerr [19], Jerrum and Snir [14], as well as recently,
including Grigoriev and Koshevoy [10], Grigoriev and Podolskii [11], Mahajan,
Nimbhorkar and Tawari [25, 26], Jukna and Seiwert [17, 18]. In fact, as shown
by Jerrum and Snir [14], if an arithmetic polynomial $P$ is multilinear and
homogeneous, then the $(\min,+)$ circuit complexity of the corresponding
minimization problem is at least the monotone arithmetic $(+,\times)$ circuit
complexity of the polynomial $P$. Thus, many other lower bounds for tropical
$(\min,+)$ circuits follow from the aforementioned earlier lower bounds on the
monotone arithmetic $(+,\times)$ circuit complexity of the corresponding
polynomials, including bounds shown many years ago by Schnorr [38], Shamir and
Snir [41], Valiant [47], Tiwari and Tompa [46] and other authors.

##  2 Results

The model of read-$k$ circuits is quite natural and is by analogy with the
intensively investigated model of _read- $k$ branching programs_. Intuitively,
“read-$k$” means that one cannot “benefit” from (multiplicative) idempotence
for more than $k$ times.

Let $F$ be a monotone Boolean $(\lor,\land)$ circuit. Throughout the article,
we assume that constants $0$ and $1$ are not are not used as inputs in Boolean
circuits: such inputs are not necessary when computing non-trivial (non-
constant) Boolean functions. An _arithmetic version_ of $F$ is a monotone
arithmetic $(+,\times)$ circuit obtained from $F$ by replacing every OR gate
with an addition gate, and every AND gate with a multiplication gate. The
obtained arithmetic circuit produces (purely syntactically) some polynomial
$P_{F}$, which we call the _formal polynomial_ of the Boolean circuit $F$. A
_shadow monomial_ of a Boolean term $t=\bigwedge_{i\in S}x_{i}$ is a monomial
$p=\prod_{i\in S}x_{i}^{d_{i}}$ with the same set of variables as $t$ and all
degrees $d_{i}\geqslant 1$. For example, $x^{2}y^{3}$ is a shadow monomial of
$xy$. It is easy to show (see Lemma 1) that the circuit $F$ computes a
monotone Boolean function $f:\\{0,1\\}^{n}\to\\{0,1\\}$ if and only if the
formal polynomial $P_{F}$ of the circuit $F$ has the following two properties:

  * (i)

every monomial of $P_{F}$ contains all variables of at least one prime
implicant of $f$;

  * (ii)

every prime implicant of $f$ has at least one shadow monomial in $P_{F}$.

Intuitively, (i) reflects the absorption property $x\lor xy=x$ (longer
monomials “do not matter”), while (ii) reflects the multiplicative idempotence
$x\land x=x$ (large degree “does not matter”). In _read_ -$k$ circuits we
strengthen the property (ii) and require that every prime implicant of $f$ has
at least one shadow monomial in $P_{F}$ in which each variable appears with
degree $\leqslant k$. There are no restrictions on the degrees of other
monomials of $P_{F}$.

######  Example 1.

The Boolean $(\lor,\land)$ circuit $F=(x\lor y)(x\lor z)(y\lor z)$ computes
the Boolean function $f(x,y,z)=1$ iff $x+y+z\geqslant 2$ (the majority
function of three variables). The arithmetic $(+,\times)$ version of $F$ is
the circuit $F^{\prime}=(x+y)(x+z)(y+z)$, and the polynomial produced by it is
$P_{F}=x^{2}y+xy^{2}+x^{2}z+y^{2}z+xz^{2}+yz^{2}+2xyz$. The (Boolean) circuit
$F$ is a read-$2$ but not a read-$1$ circuit, because, for example, both
shadow monomials $x^{2}y$ and $xy^{2}$ of the prime implicant $xy$ of $f$ in
the polynomial $P_{F}$ have a variable of degree $>1$. Note, however, that the
Boolean circuit $H=xy\lor xz\lor yz$ (the dual of the circuit $F$) also
computes $f$ but already is a read-$1$ circuit: the corresponding to this
circuit polynomial is $P_{H}=xy+xz+yz$.

Our main results are the following. A _DeMorgan circuits_ is a Boolean
$(\lor,\land,\neg)$ circuit with negations only applied to input variables.
That is, such a circuit is a monotone $(\lor,\land)$ circuit whose inputs are
variables $x_{1},\ldots,x_{n}$ and their negations
$\overline{x}_{1},\ldots,\overline{x}_{n}$. A DeMorgan $(\lor,\land,\neg)$
circuit is _multilinear_ if the two Boolean functions $g$ and $h$ computed at
the inputs to any AND gate depend on disjoint sets of variables. For example,
the functions $g=x\lor xy$ and $h=\overline{y}\lor x\overline{y}$ depend on
disjoint sets of variables: $g$ depends only on $x$, while $h$ depends only on
$y$. Every family $\mathcal{F}\subseteq 2^{[n]}$ of subsets of
$[n]:=\\{1,2,\ldots,n\\}$ defines a multilinear $n$-variate polynomial
$P_{\mathcal{F}}(x):=\sum_{S\in\mathcal{F}}\prod_{i\in S}x_{i}$. A polynomial
$Q$ is _similar_ to the polynomial $P_{\mathcal{F}}$ if it is of the form
$Q(x)=\sum_{S\in\mathcal{F}}c_{S}\prod_{i\in S}x_{i}$ for some integer
coefficients $c_{S}\geqslant 1$; in particular, the polynomial
$P_{\mathcal{F}}$ is similar to itself (then all $c_{S}=1$). An arithmetic
$(+,\times)$ circuit is _constant-free_ if it has no constants among the
inputs. We prove the following, where $\mathcal{F}\subseteq 2^{[n]}$ is an
arbitrary antichain (no two sets of $\mathcal{F}$ are comparable under the
inclusion).

  1. 1.

Read-$1$ $(\lor,\land)$ circuits are _not weaker_ than monotone _arithmetic_
$(+,\times)$ circuits computing multilinear polynomials in the following
sense: if a monotone arithmetic constant-free $(+,\times)$ circuit computes a
polynomial similar to $P_{\mathcal{F}}$, then a read-$1$ $(\lor,\land)$
circuit of the same size computes the Boolean version
$f(x)=\bigvee_{S\in\mathcal{F}}\bigwedge_{i\in S}x_{i}$ of $P_{\mathcal{F}}$.
If the polynomial $P_{\mathcal{F}}$ is homogeneous (all sets of $\mathcal{F}$
have the same number of elements), then the minimum size of a monotone
arithmetic constant-free $(+,\times)$ circuit computing a polynomial similar
to $P_{\mathcal{F}}$ even _coincides_ with the minimum size of a read-$1$
$(\lor,\land)$ circuit computing $f$ (Theorem 1).

  2. 2.

Read-$1$ $(\lor,\land)$ circuits have the _same_ power as _tropical_
$(\min,+)$ circuits in the following sense: the minimum size of a $(\min,+)$
circuit computing the tropical polynomial
$P(x)=\min_{S\in\mathcal{F}}\sum_{i\in S}x_{i}$ _coincides_ with the minimum
size of a read-$1$ $(\lor,\land)$ circuit computing the Boolean version
$f(x)=\bigvee_{S\in\mathcal{F}}\bigwedge_{i\in S}x_{i}$ of $P$ (Theorem 2).

  3. 3.

Read-$1$ $(\lor,\land)$ circuits are _not weaker_ than multilinear DeMorgan
$(\lor,\land,\neg)$ circuits in the following sense: if a multilinear
$(\lor,\land,\neg)$ circuit computes a Boolean function $f(x)$, then a
read-$1$ $(\lor,\land)$ circuit of the same size computes the monotone
function $f^{\triangledown}(x):=\bigvee_{z\leqslant x}f(z)$ (Theorem 3); note
that $f^{\triangledown}=f$ if $f$ is monotone. If the function $f$ is monotone
and homogeneous (all prime implicants of $f$ have the same number of
variables), then the minimum size of a multilinear $(\lor,\land,\neg)$ circuit
computing $f$ even _coincides_ with the minimum size of a read-$1$
$(\lor,\land)$ circuit computing $f$ (Theorem 4).

  4. 4.

Already read-$2$ $(\lor,\land)$ circuits can be exponentially smaller than
read-$1$ $(\lor,\land)$ circuits and, hence, exponentially smaller than
tropical $(\min,+)$, monotone arithmetic $(+,\times)$, and multilinear
$(\lor,\land,\neg)$ circuits (Lemma 8).

#### Organization

In the preliminary Section 3, we recall one simple but important concept—the
set of exponent vectors “produced” (purely syntactically) by a circuit over
any semiring. Read-$k$ circuits are introduced in Section 4. The
aforementioned relation of read-$1$ circuits to monotone arithmetic circuits
is established in Section 5. In Section 5.1 we recall one relatively simple
argument to show large lower bounds for monotone arithmetic $(+,\times)$
circuits; this is only aimed to demonstrate that the absence of idempotence
and absorption in such circuits is indeed a severe restriction. The relation
of read-$1$ circuits to tropical circuits is established in Section 6, and the
relation of read-$1$ circuits to multilinear DeMorgan $(\lor,\land,\neg)$
circuits is established in Section 7. An exponential gap between read-$1$ and
read-$2$ circuits is shown in Section 8. In the concluding Section 9, several
open problems are formulated. A contains a construction of so-called “blocking
lines” functions as possible candidates to attack these problems. All proofs
are fairly simple.

##  3 Preliminaries

In this section, we recall the classical model of (combinational) circuits
over arbitrary semirings, and introduce one simple but useful concept: the set
of (exponent) vectors “produced” (purely syntactically) by a circuit.

Recall that a (commutative) _semiring_ $(R,\oplus,\odot)$ consists of a set
$R$ closed under two associative and commutative binary operations “addition”
$x\oplus y$ and “multiplication” $x\odot y$, where “multiplication”
distributes over “addition:” $x\odot(y\oplus z)=(x\odot y)\oplus(x\odot z)$.
That is, in a semiring, we can “add” and “multiply,” but neither “subtraction”
nor “division” are necessarily possible. We will assume that semirings contain
a multiplicative neutral element $\mathbb{1}\in R$ such that
$x\odot\mathbb{1}=\mathbb{1}\odot x=x$.

A _circuit_ $F$ over a semiring $(R,\oplus,\odot)$ is a directed acyclic
graph; parallel edges joining the same pair of nodes are allowed. Each
indegree-zero node (an _input_ node) holds either one of the variables
$x_{1},\ldots,x_{n}$ or a semiring element $c\in R$. A circuit is _constant-
free_ if only variables $x_{1},\ldots,x_{n}$ are used as inputs. Every other
node, a _gate_ , has indegree two and performs one of the two semiring
operations $\oplus$ or $\odot$ on the values computed at the two gates
entering this gate. The _size_ of a circuit is the total number of gates in
it. A circuit $F$ _computes_ a function $f:R^{n}\to R$ if $F(x)=f(x)$ holds
for all $x\in R^{n}$.

In this article, we will consider circuits over the following three semirings
$(R,\oplus,\odot)$: the arithmetic semiring
$(\mathbb{R}_{\mbox{\footnotesize$+$}},+,\times)$, where
$\mathbb{R}_{\mbox{\footnotesize$+$}}$ is the set of nonnegative real numbers,
the tropical semiring $(\mathbb{R}_{\mbox{\footnotesize$+$}},\min,+)$, and the
Boolean semiring $(\\{0,1\\},\lor,\land)$. That is, we will consider the
following three types of circuits222An exception is Section 7, where we also
consider non-monotone Boolean $(\lor,\land,\neg)$ circuits.:

  * $\circ$

$x\oplus y:=x+y$ and $x\odot y:=xy$ (monotone arithmetic circuits);

  * $\circ$

$x\oplus y:=x\lor y$ and $x\odot y:=x\land y$ (monotone Boolean circuits);

  * $\circ$

$x\oplus y:=\min\\{x,y\\}$ and $x\odot y:=x+y$ (tropical circuits).

Note that, also over the tropical semiring, “multiplication” $(\odot)$
distributes over “addition” $(\oplus)$ because
$x+\min\\{y,z\\}=\min\\{x+y,x+z\\}$. Also, note that the multiplicative
neutral element $\mathbb{1}$ is constant $1$ in arithmetic and Boolean
semirings, but is constant $0$ in the tropical semiring (because $x+0=x$).

#### Produced polynomials

Every circuit $F(x_{1},\ldots,x_{n})$ over a semiring $(R,\oplus,\odot)$ not
only computes some function $f:R^{n}\to R$, but also _produces_ (purely
syntactically) an $n$-variate polynomial over this semiring in a natural way.
Namely, at each source node holding a constant $c\in R$, the constant
polynomial $P=c$ is produced, and at a source node holding a variable $x_{i}$,
the polynomial $P=x_{i}$ is produced. At an “addition” $(\oplus)$ gate, the
“sum” $P\oplus Q$ of the polynomials $P$ and $Q$ produced at its inputs is
produced. Finally, the polynomial produced at a “multiplication” $(\odot)$
gate is obtained from $P\odot Q$ by the distributivity of $\odot$ over
$\oplus$; that is, we “multiply” $(\odot)$ every monomial of $P$ with every
monomial of $Q$, and take the “sum” $(\oplus)$ of the obtained monomials. No
terms are canceled along the way. The polynomial produced by the entire
circuit $F$ is the polynomial $P(x)=\sum_{b\in
B}c_{b}\prod_{i=1}^{n}x_{i}^{b_{i}}$ produced at the output gate of $F$; here,
$B\subseteq\mathbb{N}^{n}$ is the set of _exponent vectors_ of the polynomial
$P$, and $x_{i}^{b_{i}}$ stands for the $b_{i}$-times “multiplication”
$x_{i}\odot x_{i}\odot\cdots\odot x_{i}$, and $x_{i}^{0}=\mathbb{1}$ (the
multiplicative neutral element). Since by our assumption, the underlying
semiring contains the multiplicative neutral element $\mathbb{1}$,
coefficients $c_{b}$ are semiring elements333Because then, by distributivity,
we have $x\oplus x=(\mathbb{1}\odot x)\oplus(\mathbb{1}\odot
x)=(\mathbb{1}\oplus\mathbb{1})x$, where $\mathbb{1}\oplus\mathbb{1}$ _is_ a
semiring element. An example, where this is not the case is the semiring
$(R,+,\times)$ with $R\subset\mathbb{N}$ being the set of all even integers:
then the coefficient “$3$” of $x+x+x=3x$ is not a semiring element..

######  Remark 1.

Let us stress the difference between what circuits _compute_ (as functions)
and what they actually _produce_ (as formal expressions). The point is that,
unlike when computing polynomial _functions_ , no terms are canceled when
_producing_ polynomials. Thus, the polynomial function $f$ _computed_ by a
circuit $F$ may be different from the produced polynomial $P$ due to apparent
cancellations of some terms of $P$: unlike for the polynomial $P$ (which only
depends on the circuit $F$ itself), the function $f$ computed by $F$ already
depends on the underlying semiring. For example, over the arithmetic semiring
$(\mathbb{R},+,\times)$, the polynomial produced by the circuit $F=(x+y)(x-y)$
is $P=x^{2}+c_{1}xy+c_{2}y^{2}$ with the set $B=\\{(2,0),(1,1),(0,2)\\}$ of
exponent vectors, and coefficients $c_{1}=1-1=0$ and $c_{2}=-1$, while the
polynomial function _computed_ by the circuit $F$ is $f=x^{2}-y^{2}$ whose set
of exponent vectors is $A=\\{(2,0),(0,2)\\}$. Note, however, that in monotone
Boolean $(\lor,\land)$ and tropical $(\min,+)$ circuits we have no
cancellations like arithmetic $x-x=0$ because there are no analogs of
arithmetic subtraction in the corresponding semirings. In these circuits, we
only have cancellations via absorption $x\lor xy=x$ or $\min\\{x,x+y\\}=x$
when going from the _produced_ polynomials $P$ to the functions $f$ actually
_computed_ by the circuits. In monotone arithmetic $(+,\times)$ circuits we
have no cancellations at all: then $f=P$ (as formal expressions, see Fact 1 in
Section 5).

#### Produced sets of exponent vectors

Of interest for us will be not as much the polynomials $P(x)=\sum_{b\in
B}c_{b}\prod_{i=1}^{n}x_{i}^{b_{i}}$ produced by circuits $F$ themselves but
rather the sets $B=B_{F}\subseteq\mathbb{N}^{n}$ of exponent vectors of these
polynomials. These sets can be inductively obtained as follows, where
$\vec{0}$ is the all-$0$ vector, and $\vec{e}_{i}\in\\{0,1\\}^{n}$ has exactly
one $1$ in the $i$th position:

  * $\circ$

if $F=c\in R$ (a constant), then $B_{F}=\\{\vec{0}\\}$;

  * $\circ$

if $F=x_{i}$ (input variable), then $B_{F}=\\{\vec{e}_{i}\\}$;

  * $\circ$

if $F=G\oplus H$, then $B_{F}=B_{G}\cup B_{H}$ (set-theoretic union);

  * $\circ$

if $F=G\odot H$, then $B_{F}=B_{G}+B_{H}:=\\{a+b\colon a\in B_{G},b\in
B_{H}\\}$ (Minkowski sum).

Since the set of exponent vectors of a “product” $(\odot)$ of two polynomials
is the Minkowski sum of their sets of exponent vectors, and since no
cancellations are performed when producing polynomials, the set
$B_{F}\subseteq\mathbb{N}^{n}$ of vectors produced by a circuit $F$ is the set
of exponent vectors of the polynomial produced by the circuit $F$.

It is clear that the same circuit with “addition” $(\oplus$) and
“multiplication” $(\odot)$ gates can compute _different_ functions over
different semirings. Say, the circuit $F=(x\odot y)\oplus z$ computes $xy+z$
over the arithmetic $(+,\times)$ semiring, but computes $\min\\{x+y,z\\}$ over
the tropical $(\min,+)$ semiring, and computes the Boolean function $xy\lor z$
over the Boolean $(\lor,\land)$ semiring. It is, however, important to note
that:

  * $\circ$

The set $B_{F}\subseteq\mathbb{N}^{n}$ of exponent vectors of the polynomial
_produced_ by a circuit $F$ over any semiring is always the same—it only
depends on the circuit $F$ itself, not on the underlying semiring.

This simple observation turned out to be useful when comparing the powers of
circuits over _different_ semirings.

######  Notation.

We will use standard terminology and notation regarding Boolean functions
(see, for example, the books by Wegener [48] or Crama and Hammer [7]). In
particular, for two Boolean functions $f,g:\\{0,1\\}^{n}\to\\{0,1\\}$, we
write $g\leqslant f$ iff $g(a)\leqslant f(a)$ holds for all
$a\in\\{0,1\\}^{n}$. A Boolean _term_ is an AND of a nonempty set of
_literals_ , each being a variable $x_{i}$ or its negation $\overline{x}_{i}$.
A term is a _zero term_ if it contains a variable and its negation. An
_implicant_ of a Boolean function $f(x_{1},\ldots,x_{n})$ is a nonzero term
$t$ such that $t\leqslant f$ holds, that is, $t(a)=1$ implies $f(a)=1$. An
implicant $t$ of $f$ is a _prime implicant_ of $f$ if no proper subterm
$t^{\prime}$ of $t$ has this property, that is, if $t\leqslant
t^{\prime}\leqslant f$ implies $t^{\prime}=t$. For example, if $f=xy\lor
x\overline{y}z$, then $xy$, $x\overline{y}z$ and $xz$ are implicants of $f$,
but $x\overline{y}z$ is not a prime implicant (since $x\overline{y}z\leqslant
xz\leqslant f$). A Boolean function $f$ is _monotone_ if $a\leqslant b$
implies $f(a)\leqslant f(b)$. It is well known and easy to show (see, for
example, [7, Theorem 1.21]) that prime implicants of monotone Boolean
functions do not contain negated variables.

##  4 Read-k Circuits

A monotone Boolean circuit is a circuit over the Boolean semiring
$(R,\oplus,\odot)$ with $x\oplus y:=x\lor y$ and $x\odot y:=x\land y$; the
domain is $R=\\{0,1\\}$. To avoid trivialities, we will only consider monotone
Boolean circuits computing _non-constant_ Boolean functions $f$. In every
$(\lor,\land)$ circuit computing such a function $f$, constant inputs $0$ and
$1$ can be easily eliminated without increasing the circuit size by
iteratively applying $1\land x=x$, $0\land x=0$, $1\lor x=1$ and $0\lor x=x$.
Thus:

  * $\circ$

We will always (implicitly) assume that monotone Boolean $(\lor,\land)$
circuits are _constant-free_ , that is, have no constants $0$ or $1$ as
inputs.

Let us fix some notation. The _support_ of a vector $a\in\mathbb{N}^{n}$ is
the set

$\mathrm{sup}(a):=\\{i\in[n]\colon a_{i}\neq 0\\}$

of its nonzero positions. For a set $A\subseteq\mathbb{N}^{n}$ of vectors, let

$\mathrm{Sup}(A):=\\{\mathrm{sup}(a)\colon a\in A\\}\subseteq 2^{[n]}$

denote the family of supports of vectors of $A$. The _upward closure_ of a set
$A\subseteq\mathbb{N}^{n}$ of vectors is the set

$A^{\uparrow}:=\\{b\in\mathbb{N}^{n}\colon\mbox{$b\geqslant a$ for some $a\in
A$}\\}$

of vectors containing at least one vector of $A$; a vector $b$ _contains_ a
vector $a$ if $b_{i}\geqslant a_{i}$ holds for all positions
$i\in\\{1,\ldots,n\\}$.

Now let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ be a monotone Boolean function A _lowest
one_ of $f$ is a vector $a\in\\{0,1\\}^{n}$ such that $f(a)=1$ but $f(b)=0$
for every vector $b\leqslant a$, $b\neq a$. We will denote the set of all
lowest ones of $f$ by $A_{f}$. Note that the set $A_{f}$ is always an
_antichain_ : $a,b\in A_{f}$ and $b\leqslant a$ imply $a=b$. Since the
function $f$ is monotone, for every input vector $x\in\\{0,1\\}^{n}$, we have

$f(x)=1$ iff $x\geqslant a$ for some $a\in A_{f}$ iff
$x\in(A_{f})^{\uparrow}$.

It is also easy to see that $a\in f^{-1}(1)$ iff the term
$t_{a}=\bigwedge_{i\in\mathrm{sup}(a)}x_{i}$ is an implicant of $f$. Thus,
$a\in A_{f}$ iff the term $t_{a}$ is a _prime_ implicant of $f$. It is,
therefore, useful to keep in mind that if we view implicants of $f$ as sets of
their variables, then

$A_{f}=\mbox{ set of characteristic $0$-$1$ vectors of prime implicants of
$f$.}$

For example, if $f=xz\lor y$, then $A_{f}=\\{(1,0,1),(0,1,0)\\}$. Let us
stress that the only reason why we use such a “vector-representation” of prime
implicants is to _unify_ (and simplify) the forthcoming comparisons of the
powers of _different_ types of circuits: Boolean, arithmetic and tropical.

Our starting point is the following simple structural property of sets of
exponent vectors produced by monotone Boolean circuits.

######  Lemma 1 (Folklore).

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ be a monotone Boolean function, $F$ be a
monotone Boolean $(\lor,\land)$ circuit, and $B_{F}\subseteq\mathbb{N}^{n}$ be
the set of exponent vectors produced by $F$. Then the following two assertions
are equivalent.

  * (i)

The circuit $F$ computes $f$.

  * (ii)

Inclusions $\mathrm{Sup}(A_{f})\subseteq\mathrm{Sup}(B_{F})$ and
$B_{F}\subseteq(A_{f})^{\uparrow}$ hold.

###### Proof.

Let $A:=A_{f}$ and $B:=B_{F}$. Our Boolean function $f$ is of the form
$f(x)=\bigvee_{a\in A}\bigwedge_{i\in\mathrm{sup}(a)}x_{i}$, and the Boolean
function computed by the circuit $F$ is of the form $F(x)=\bigvee_{b\in
B}~{}\bigwedge_{i\in\mathrm{sup}(b)}x_{i}$. The (ii) $\Rightarrow$ (i)
implication directly follows from a simple observation: for every input
$x\in\\{0,1\\}^{n}$, we have $f(x)=1$ iff
$\mathrm{sup}(x)\supseteq\mathrm{sup}(a)$ holds for some $a\in A$. Hence,
$B\subseteq A^{\uparrow}$ yields $F(x)\leqslant f(x)$, while
$\mathrm{Sup}(A)\subseteq\mathrm{Sup}(B)$ yields $f(x)\leqslant F(x)$.

To show the (i) $\Rightarrow$ (ii) implication, assume that the circuit $F$
computes $f$. If $b\not\in A^{\uparrow}$ held for some vector $b\in B$, then
we would have $\mathrm{sup}(a)\setminus\mathrm{sup}(b)\neq\emptyset$ for all
$a\in A$. But then, on the input $x\in\\{0,1\\}^{n}$ with $x_{i}=1$ iff
$i\in\mathrm{sup}(b)$, we would have $f(x)=0$ while $F(x)=1$, a contradiction.
To show the inclusion $\mathrm{Sup}(A)\subseteq\mathrm{Sup}(B)$, suppose for
the sake of contradiction that there is a vector $a\in A$ such that
$\mathrm{sup}(b)\neq\mathrm{sup}(a)$ holds for all vectors $b\in B$. Since
$B\subseteq A^{\uparrow}$, $a^{\prime}\leqslant b$ holds for some vector
$a^{\prime}\in A$. So, the proper inclusion
$\mathrm{sup}(b)\subset\mathrm{sup}(a)$ cannot hold, for otherwise, we would
have $\mathrm{sup}(a^{\prime})\subseteq\mathrm{sup}(b)\subset\mathrm{sup}(a)$
and, hence, also $a^{\prime}\leqslant a$ and $a^{\prime}\neq a$, a
contradiction with the set $A$ being an antichain. So, we have
$\mathrm{sup}(b)\setminus\mathrm{sup}(a)\neq\emptyset$ for all vectors $b\in
B$. But then $F(a)=0$ while $f(a)=1$, a contradiction.

A _shadow_ of a vector $x\in\mathbb{R}^{n}$ is a vector $y\in\mathbb{R}^{n}$
with $\mathrm{sup}(x)=\mathrm{sup}(y)$ (with the same set of nonzero positions
as $x$). The inclusion $\mathrm{Sup}(A_{f})\subseteq\mathrm{Sup}(B_{F})$ in
Lemma 1 means that every lowest one of $f$ has at least one shadow in $B_{F}$.
In general, these shadows may have large entries, even exponential in the
circuit size. In read-$k$ circuits, we restrict the magnitude of entries of
shadows. Say that a vector $b\in\mathbb{N}^{n}$ is $k$-_bounded_ if
$b_{i}\leqslant k$ holds for all $i\in\mathrm{sup}(b)$.

######  Definition 1 (Read-$k$ circuits).

Let $F$ be a monotone $(\lor,\land)$ circuit, and
$B_{F}\subseteq\mathbb{N}^{n}$ be the set of exponent vectors produced by $F$.
The circuit $F$ is a _syntactically read- $k$ circuit_ if all vectors of
$B_{F}$ are $k$-bounded, and is a (semantically) _read- $k$ circuit_ if every
lowest one of the Boolean function $f:\\{0,1\\}^{n}\to\\{0,1\\}$ computed by
$F$ has at least one $k$-bounded shadow in $B_{F}$. In particular, $F$ is a
read-$1$ circuit iff the inclusions $A_{f}\subseteq
B_{F}\subseteq(A_{f})^{\uparrow}$ hold.

Thus, $F$ is a (semantically) read-$k$ circuit if
$\mathrm{Sup}(A_{f})\subseteq\mathrm{Sup}(B_{F}\cap\\{0,1,\ldots,k\\}^{n})$
holds, and is a syntactically read-$k$ circuit if also
$B_{F}\subseteq\\{0,1,\ldots,k\\}^{n}$ holds. It is clear that every
syntactically read-$k$ circuit is also a (semantically) read-$k$ circuit, but
not the vice versa. Intuitively, a monotone circuit $F$ computing a monotone
Boolean function $f$ is a read-$k$ circuit444The term “read-$k$ circuit” is by
analogy with the well-known term “read-$k$ times branching program;” see the
discussion at the end of Section 9 (after Problem 3). if it can distinguish
each vector $a\in A_{f}\subseteq f^{-1}(1)$ from all vectors in $f^{-1}(0)$ by
“reading/accessing” each $1$-entry of the vector $a$ at most $k$ times.

For a monotone Boolean function $f$, let

$\displaystyle\mathsf{B}_{k}(f):=$ min size of a monotone read-$k$
$(\lor,\land)$ circuit computing $f$.

######  Remark 2.

Note that already read-$1$ circuits are “universal:” every monotone Boolean
function $f$ _can_ be computed by a read-$1$ circuit, and even, by a
_syntactically_ read-$1$ circuit, for example, as an OR of all prime
implicants of $f$. But read-$k$ circuits for small $k$ can be very
inefficient: we will show in Section 8 that already the gap
$\mathsf{B}_{1}(f)/\mathsf{B}_{2}(f)$ can be exponential.

###  4.1 Viewing Boolean Circuits as Arithmetic Circuits

As we already mentioned in Section 2, an equivalent and, apparently, more
intuitive definition of read-$k$ $(\lor,\land)$ circuits comes by looking at
their arithmetic versions. An arithmetic circuit is _constat-free_ if it has
no constants as inputs. The _arithmetic $(+,\times)$ version_ of a monotone
Boolean $(\lor,\land)$ circuit $F$ is the constant-free $(+,\times)$ circuit
obtained by replacing $\lor$-gates with $+$-gates, and $\land$-gates with
$\times$-gates. That is, we replace the “addition” gates by “addition” gates,
and “multiplication” gates by “multiplication” gates of the corresponding
semirings. A _shadow monomial_ of a Boolean term $\bigwedge_{i\in S}x_{i}$ is
a monomial $\prod_{i\in S}x_{i}^{d_{i}}$ with $d_{i}\geqslant 1$ for all $i\in
S$.

The _formal polynomial_ of a monotone Boolean $(\lor,\land)$ circuit $F$ is
the polynomial $P_{F}(x)=\sum_{b\in B_{F}}c_{b}\prod_{i=1}^{n}x_{i}^{b_{i}}$
produced by the arithmetic $(+,\times)$ version of $F$. Lemma 1 implies that
the circuit $F$ computes a (monotone) Boolean function
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ iff the formal polynomial $P_{F}$ of $F$ has the
following two properties.

  * (i)

Absorption $x\lor xy=x$: for every monomial $\prod_{i=1}^{n}x_{i}^{b_{i}}$ of
$P_{F}$, the Boolean term $\bigwedge_{i\in\mathrm{sup}(b)}x_{i}$ is an
implicant of $f$; this is the property $B_{F}\subseteq(A_{f})^{\uparrow}$ in
Lemma 1.

  * (ii)

Idempotence $x\land x=x$: every prime implicant of $f$ has at least one shadow
monomial in $P_{F}$; this is the property
$\mathrm{Sup}(A_{f})\subseteq\mathrm{Sup}(B_{F})$ in Lemma 1.

In read-$k$ circuits, the degree of variables in shadow monomials guaranteed
by (ii) is restricted The _individual degree_ of a monomial is the maximum
degree of its variable.

######  Definition 2 (Arithmetic equivalent of 1).

A monotone $(\lor,\land)$ circuit $F$ is a _read- $k$_ circuit if every prime
implicant of $f$ has at least one shadow monomial in $P_{F}$ of individual
degree $\leqslant k$. If the individual degree of _every_ monomial of $P_{F}$
is $\leqslant k$, then $F$ is a _syntactically read- $k$_ circuit.

######  Remark 3.

If $G$ and $H$ are monotone $(\lor,\land)$ circuits, then the formal
polynomial of the circuit $F=G\lor H$ is $P_{F}=P_{G}+P_{H}$, and the formal
polynomial of the circuit $F=G\land H$ is $P_{F}=P_{G}\cdot P_{H}$. If
$g,h:\\{0,1\\}^{n}\to\\{0,1\\}$ are the (monotone) Boolean functions computed
by the circuits $G$ and $H$, then every prime implicant of $g\lor h$ is a
prime implicant of $g$ or of $h$, and every prime implicant of $g\land h$ is
the AND of some prime implicant of $g$ and some prime implicant of $h$. Thus,
the OR of two read-$k$ circuits is again a read-$k$ circuit, while the AND of
such circuits is a read-$r$ circuit for some $k\leqslant r\leqslant 2k$. In
particular, the “read parameter” $k$ does not increase at OR gates: it can
only increase at AND gates.

###  4.2 Reducing the total degree

If $F$ is a _syntactically_ read-$k$ $(\lor,\land)$ circuit computing a
monotone Boolean function $f:\\{0,1\\}^{n}\to\\{0,1\\}$, then all monomials of
the formal polynomial $P_{F}$ of $F$ have degree555As customary, the _degree_
of a monomial $\prod_{i=1}^{n}x_{i}^{b_{i}}$ is the sum $b_{1}+\cdots+b_{n}$
of the degrees of its variables. Note that, if a monomial has individual
degree $\leqslant k$, then its degree is $\leqslant kn$. The _degree_
$\mathrm{deg}(P)$ of a polynomial is the maximum degree of its monomial.
$\leqslant kn$. However, if $F$ is a (not necessarily syntactically) read-$k$
circuit, then only shadow monomials in the formal polynomial $P_{F}$ must have
degree $\leqslant kn$: in this case, the polynomial $P_{F}$ may also have
other “redundant” monomials of very large degree, up to $2^{r}n$ where $r$ is
the maximum number of AND gates along an input-output path in the circuit $F$;
about such monomials of $P_{F}$ we only know property (i) above.

Still, using a simple observation, usually attributed to Strassen [43] (see,
for example, [42, Theorem 2.2]), one can show that the degree of _all_
monomials in $P_{F}$ can be decreased till $kn$. For a polynomial $P$ of
degree $d$, let ${P}[i]$ be the sub-polynomial of $P$ consisting of monomials
of degree exactly $i$; hence, $P={P}[0]+{P}[1]+\cdots+{P}[d]$.

######  Homogenization Lemma (Strassen [43]).

If a polynomial $P$ of degree $d$ can be produced by an arithmetic circuit of
size $s$, then for every $r\leqslant d$ all homogeneous parts
${P}[0],{P}[1],\ldots,{P}[r]$ of $P$ can be simultaneously produced by an
arithmetic circuit of size $\text{O}(sr^{2})$.

###### Proof sketch.

The idea is very simple. Take an arbitrary $i\in\\{0,1,\ldots,r\\}$. If
$P=Q+R$, then ${P}[i]={Q}[i]+{R}[i]$, and if $P=Q\cdot R$, then
${P}[i]=\sum_{j=0}^{i}{Q}[j]\cdot{R}[i-j]$. So, we can take $r+1$ copies
$v_{0},v_{1},\ldots,v_{r}$ of each gate $v$ and connect them accordingly so
that at $v_{i}$ the homogeneous sub-polynomial of total degree $i$ of the
polynomial produced at the gate $v$ is produced. Every addition $(+)$ gate is
replaced by $r+1$ addition gates, and each multiplication $(\times)$ gate is
replaced by $\sum_{i=0}^{r}(2i+1)=(r+1)^{2}$ gates. Thus, the obtained circuit
has at most $s(r+1)^{2}$ gates.

The following easy consequence of this lemma shows that, at the cost of a
relatively small increase in circuit size, we can assume that formal
polynomials of read-$k$ circuits have degree $\leqslant kn$.

######  Lemma 2.

Let $f(x_{1},\ldots,x_{n})$ be a monotone Boolean function, and $m$ be the
maximal number of variables in a prime implicant of $f$. If $f$ can be
computed by a read-$k$ circuit $F$ of size $s$, then $f$ can also be computed
by a read-$k$ circuit $H$ of size at most $s$ times $\text{O}(k^{2}m^{2})$
whose formal polynomial $P_{H}$ has degree $\mathrm{deg}(P_{H})\leqslant km$.

###### Proof.

Let $A:=A_{f}$ be the set of the lowest ones of $f$, that is, of
characteristic $0$-$1$ vectors of prime implicants of $f$. Since, by our
assumption, no prime implicant of $f$ has more than $m$ variables, we have
$|\mathrm{sup}(a)|\leqslant m$ for all $a\in A$. Suppose that the function $f$
can be computed by a read-$k$ $(\lor,\land)$ circuit $F$ of size $s$, and let
$P(x)=\sum_{b\in B}c_{b}\prod_{i=1}^{n}x_{i}^{b_{i}}$ be the polynomial
produced by the arithmetic $(+,\times)$ version of the circuit $F$; hence,
$P=P_{F}$ is the formal polynomial of the circuit $F$. Since the circuit $F$
computes the function $f$, Lemma 1 gives us the inclusions
$\mathrm{Sup}(A)\subseteq\mathrm{Sup}(B)$ and $B\subseteq A^{\uparrow}$.

Consider the sub-polynomial $P^{\prime}(x):=\sum_{b\in
B^{\prime}}c_{b}\prod_{i=1}^{n}x_{i}^{b_{i}}$ of $P$ whose set of exponent
vectors is $B^{\prime}=\\{b\in B\colon b_{1}+\cdots+b_{n}\leqslant km\\}$.
That is, the polynomial $P^{\prime}={P}[0]+{P}[1]+\cdots+{P}[km]$ consists of
all terms of $P$ of degree $\leqslant km$; hence,
$\mathrm{deg}(P^{\prime})\leqslant km$. Since the circuit $F$ is a read-$k$
circuit, for every lowest one $a\in A_{f}$ there is a monomial
$\prod_{i=1}^{n}x_{i}^{b_{i}}$ in $P$ (a shadow of $a$) with
$\mathrm{sup}(b)=\mathrm{sup}(a)$ and $b_{i}\leqslant k$ for all
$i\in\mathrm{sup}(b)$. Since then $b_{1}+\cdots+b_{n}\leqslant
k|\mathrm{sup}(a)|\leqslant km$, the polynomial $P^{\prime}$ contains shadows
of _all_ prime implicants of $f$. This is a crucial property that gives us the
inclusion $\mathrm{Sup}(A)\subseteq\mathrm{Sup}(B^{\prime})$.

Since the polynomial $P$ can be produced by a $(+,\times)$ circuit of size
$s$, Strassen’s homogenization lemma implies that the sub-polynomial
$P^{\prime}$ of $P$ can be produced by an arithmetic $(+,\times)$ circuit
$F^{\prime}$ of size $\text{O}(sk^{2}m^{2})$. Let $H$ be the Boolean
$(\lor,\land)$ version of the circuit $F^{\prime}$ obtained by replacing $+$
gates by $\lor$-gates, and $\times$ gates by $\land$-gates. That is, we
replace the “addition” gates by “addition” gates, and “multiplication” gates
by “multiplication” gates of the corresponding semirings. The polynomial
$P^{\prime}$ is the formal polynomial $P_{H}$ of the circuit $H$. In
particular, $\mathrm{deg}(P_{H})=\mathrm{deg}(P^{\prime})\leqslant km$. The
set of “exponent” vectors produced by the circuit $H$ is the set $B^{\prime}$
of exponent vectors produced by the circuit $F^{\prime}$. Hence, the Boolean
function computed by $H$ is the Boolean version $h(x)=\bigvee_{b\in
B^{\prime}}\bigwedge_{i\in\mathrm{sup}(b)}x_{i}$ of the polynomial
$P^{\prime}(x)=\sum_{b\in B^{\prime}}c_{b}\prod_{i=1}^{n}x_{i}^{b_{i}}$
produced by $F^{\prime}$. Since
$\mathrm{Sup}(A)\subseteq\mathrm{Sup}(B^{\prime})$ and $B^{\prime}\subseteq
B\subseteq A^{\uparrow}$, Lemma 1 implies that the _function_ $h$ is the same
as our function $f$. Since the $(\lor,\land)$ circuit $F$ was a read-$k$
circuit, the circuit $H$ is also a read-$k$ circuit.

##  5 From Monotone Arithmetic to Boolean Read-1

A monotone arithmetic $(+,\times)$ circuit is a circuit over the arithmetic
semiring $(R,\oplus,\odot)$ with $x\oplus y:=x+y$ (arithmetic addition) and
$x\odot y:=x\times y$ (arithmetic multiplication); the domain is the set
$R=\mathbb{R}_{\mbox{\footnotesize$+$}}$ of all _nonnegative_ real numbers;
hence, the adjective “monotone:” since there are no negative constant inputs
(like $-1$), there are no cancellations $x-x=0$. The main difference of
monotone arithmetic $(+,\times)$ circuits from Boolean and tropical circuits
is that they “produce what they compute.”

This can be easily shown using the following extension to multivariate
polynomials of a basic fact that no univariate polynomial of degree $d$ can
have more than $d$ roots (see, for example, Alon and Tarsi [2, Lemma 2.1]): If
$P$ is a nonzero $n$-variate polynomial in which every variable has degree
$\leqslant d$, and if $S\subseteq\mathbb{R}$ is a set of $|S|\geqslant d+1$
numbers, then $P(x)\neq 0$ holds for at least one point $x\in S^{n}$. This is
proved in [2] by an easy induction on the number $n$ of variables, an gives
the following property of monotone arithmetic circuits.

######  Fact 1.

If a monotone arithmetic circuit _computes_ a given polynomial, then the
circuit also _produces_ that polynomial.

###### Proof.

Let $F$ be a monotone arithmetic $(+,\times)$ circuit computing a polynomial
$P$, and let $Q$ be the polynomial produced by $F$. Since the circuit $F$ is
monotone, it has no negative constants as inputs. So, the coefficients in both
polynomials $P$ and $Q$ are positive. Suppose for the sake of contradiction
that the polynomials $P$ and $Q$ do not coincide (as formal expressions). Then
$P-Q$ is a nonzero polynomial of a (possibly large but) _finite_ degree $d$.
By taking any set $S\subseteq\mathbb{N}$ of $|S|\geqslant d+1$ numbers, the
aforementioned result of Alon and Tarsi implies that $P(x)-Q(x)\neq 0$ for
some $x\in S^{n}$, a contradiction with our assumption that the circuit $F$
computes the polynomial $P$.

Say that a polynomial $Q$ is _similar_ to a polynomial $P_{A}(x)=\sum_{a\in
A}\prod_{i=1}^{n}x_{i}^{a_{i}}$ if it is of the form $Q(x)=\sum_{a\in
A}c_{a}\prod_{i=1}^{n}x_{i}^{a_{i}}$ for some positive integer coefficients
$c_{a}\geqslant 1$ (note that the set $A$ of exponent vectors of $Q$ is the
_same_ as that of $P_{A}$). In particular, the polynomial $P_{A}$ is similar
to itself. Recall that an arithmetic circuit is _constant-free_ if it has no
constants as inputs. For a set $A\subseteq\mathbb{N}^{n}$ of vectors, let

$\displaystyle\mathsf{Arith}(A):=$ min size of a monotone arithmetic constant-
free $(+,\times)$ circuit producing a polynomial similar to
$P_{A}(x)=\sum_{a\in A}\prod_{i=1}^{n}x_{i}^{a_{i}}$.

In particular, $\mathsf{Arith}(A)$ is a lower bound on the size of any
monotone arithmetic $(+,\times)$ circuit computing the polynomial
$P_{A}(x)=\sum_{a\in A}\prod_{i=1}^{n}x_{i}^{a_{i}}$.

The model of monotone arithmetic $(+,\times)$ circuits has been studied in
many papers, including [8, 9, 14, 17, 33, 38, 41, 46, 47]. Strong, even
exponential lower bounds on $\mathsf{Arith}(A)$ for explicit sets
$A\subseteq\\{0,1\\}^{n}$ are known. Already in 1976, Schnorr [38] has proved
that $\mathsf{Arith}(A)\geqslant|A|-1$ holds for every set
$A\subseteq\mathbb{N}^{n}$ which is _cover-free_ in that $a+b\geqslant c$ with
$a,b,c\in A$ implies $c\in\\{a,b\\}$. For example, any set
$A\subseteq\\{0,1\\}^{n}$ of vectors with $m$ ones, no two of which share
$\lfloor m/2\rfloor$ ones in common, is cover-free. Also, as shown in [38],
the set of characteristic $0$-$1$ vectors of cliques in $K_{n}$ (viewed as
sets of their edges) on the same number of vertices is also cover-free.

Gashkov and Sergeev [9] substantially extended Schnorr’s result by showing
that $\mathsf{Arith}(A)\geqslant|A|/\max\\{t^{3},s^{2}\\}-1$ holds for every
set $A\subseteq\mathbb{N}^{n}$ which is $(t,s)$-_thin_ in the following sense:
for every sets $X,Y\subseteq\mathbb{N}^{n}$ of vectors, the inclusion
$X+Y\subseteq A$ implies $|X|\leqslant t$ or $|Y|\leqslant s$. It is easy to
see that cover-free sets are $(1,1)$-thin sets666Suppose that a set $A$ is
_not_ a $(1,1)$-thin set. Then the inclusion
$\\{x,x^{\prime}\\}+\\{y,y^{\prime}\\}\subseteq A$ holds for some vectors
$x\neq x^{\prime}$ and $y\neq y^{\prime}$. But then the sum
$(x+y)+(x^{\prime}+y^{\prime})$ of two vectors of $A$ contains a third vector
$x+y^{\prime}$ of $A$, meaning that $A$ is _not_ a cover-free set.. Together
with the construction of $(t,t!)$-thin sets $A\subseteq\\{0,1\\}^{n}$ by
Kollár, Rónyai and Szabó [20] (via so-called _norm-graphs_), this yields the
best known lower bound $\mathsf{Arith}(A)\geqslant 2^{n/2-o(n)}$ on the size
of monotone arithmetic circuits computing any polynomial similar to the
explicit multilinear polynomial $P(x)=\sum_{a\in
A}\prod_{i=1}^{n}x_{i}^{a_{i}}$ (see [9, Theorem 3] or [17, Appendix E] for
more details).

On the other hand, monotone Boolean read-$k$ $(\lor,\land)$ circuits and
monotone arithmetic $(+,\times)$ circuits are interrelated. By Fact 1,
monotone $(+,\times)$ circuits produce what they compute. Hence, Lemma 1
implies that for every monotone Boolean function $f:\\{0,1\\}^{n}\to\\{0,1\\}$
and for any $k\geqslant 1$, we have

$\mathsf{B}_{k}(f)=\min\left\\{\mathsf{Arith}(B)\colon\mbox{
$\mathrm{Sup}(A_{f})\subseteq\mathrm{Sup}(B\cap\\{0,1,\ldots,k\\}^{n})$ and
$B\subseteq(A_{f})^{\uparrow}$}\right\\}\,.$ (1)

In particular, for every monotone Boolean function
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ and for every integer $k\geqslant 1$ there is a
set $B\subseteq\mathbb{N}^{n}$ of vectors satisfying the conditions in Eq. 1
such that $\mathsf{B}_{k}(f)\geqslant\mathsf{Arith}(B)$ holds, that is,
$\mathsf{B}_{k}(f)$ is at least the minimum size of a monotone arithmetic
constant-free $(+,\times)$ circuit computing a polynomial similar to
$P(x)=\sum_{b\in B}\prod_{i=1}^{n}x_{i}^{b_{i}}$. Thus, at least in principle,
lower bounds on the size of Boolean read-$k$ $(\lor,\land)$ circuits _can_ be
obtained by proving lower bounds on the size of monotone arithmetic
$(+,\times)$ circuits. The problem, however, is that we know only little about
the structure of the sets $B\subseteq\mathbb{N}^{n}$ of exponent vectors of
the polynomial to be considered: we only know that the two inclusions in Eq. 1
hold. Fortunately, for $k=1$ (read-once circuits), the situation is much
better: it is then enough to prove that $\mathsf{Arith}(B)$ is large for the
so-called “lower envelope” $B\subseteq A_{f}$ of the (known to us) set
$A_{f}$.

The _lower envelope_ $\lfloor B\rfloor\subseteq B$ of a set
$B\subseteq\mathbb{N}^{n}$ of vectors consists of all vectors $b\in B$ of the
smallest degree, where the _degree_ of a vector $b\in\mathbb{N}^{n}$ is the
sum $|b|:=b_{1}+\cdots+b_{n}$ of its entries. Note that for a monotone Boolean
function $f$, $\lfloor A_{f}\rfloor$ is the set of characteristic $0$-$1$
vectors of _shortest_ implicants of $f$ (those with the smallest number of
variables). A set $B\subseteq\mathbb{N}^{n}$ is _homogeneous_ of degree $m$,
if all its vectors have the same degree $m$; note that then $\lfloor
B\rfloor=B$ holds.

If $d$ is the minimum degree of a vector in $B$, then Strassen’s
homogenization lemma (see Section 4.2) implies that $\mathsf{Arith}(\lfloor
B\rfloor)$ is at most $\mathsf{Arith}(B)$ times $\text{O}(d^{2})$. However,
this additional factor $\text{O}(d^{2})$ can be eliminated using the fact that
the set $B$ contains no vectors of degree _smaller_ than $d$.

######  Envelope Lemma (Jerrum and Snir [14]).

For every $B\subseteq\mathbb{N}^{n}$, $\mathsf{Arith}(\lfloor
B\rfloor)\leqslant\mathsf{Arith}(B)$.

###### Proof.

Take a monotone arithmetic constant-free $(+,\times)$ circuit $F$ of size
$s=\mathsf{Arith}(B)$ computing some polynomial $Q(x)=\sum_{b\in
B}c_{b}\prod_{i=1}^{n}x_{i}^{b_{i}}$ similar to the polynomial
$P(x)=\sum_{b\in B}\prod_{i=1}^{n}x_{i}^{b_{i}}$. By Fact 1, the circuit $F$
also _produces_ the polynomial $Q$. The polynomial
$Q^{\prime}(x)=\sum_{b\in\lfloor B\rfloor}c_{b}\prod_{i=1}^{n}x_{i}^{b_{i}}$
is similar to the polynomial $P^{\prime}(x)=\sum_{b\in\lfloor
B\rfloor}\prod_{i=1}^{n}x_{i}^{b_{i}}$. Hence, it is enough to show that the
polynomial $Q^{\prime}$ can also be produced by a monotone arithmetic
constant-free $(+,\times)$ circuit $F^{\prime}$ of size at most $s$.

We will obtain the desired circuit $F^{\prime}$ from the circuit $F$ by
appropriately discarding some of the edges entering $+$-gates. For a gate $v$
in the circuit $F$, let $B_{v}\subseteq\mathbb{N}^{n}$ be the set of exponent
vectors of the polynomial produced at $v$, and let $\mathrm{dg}(v)$ denote the
_minimum_ degree $b_{1}+\cdots+b_{n}$ of a vector $b\in B_{v}$. Note that
$B_{v}=B$ holds for the output gate $v$ of $F$.

If $v=u\times w$ is a multiplication gate, then $B_{v}=B_{u}+B_{w}$ (Minkowski
sum). Since the degree of a sum of two vectors is the sum of their degrees, we
have $\mathrm{dg}(v)=\mathrm{dg}(u)+\mathrm{dg}(w)$ and, hence, also $\lfloor
B_{v}\rfloor=\lfloor B_{u}+B_{w}\rfloor=\lfloor B_{u}\rfloor+\lfloor
B_{w}\rfloor$. So, we do nothing in this case. If $v=u+w$ is an addition gate,
then $B_{v}=B_{u}\cup B_{w}$. If $\mathrm{dg}(u)=\mathrm{dg}(w)$, then
$\lfloor B_{v}\rfloor=\lfloor B_{u}\cup B_{w}\rfloor=\lfloor
B_{u}\rfloor\cup\lfloor B_{w}\rfloor$, and we also do nothing in this case.
However, if $\mathrm{dg}(u)<\mathrm{dg}(w)$, then $\lfloor
B_{v}\rfloor=\lfloor B_{u}\cup B_{w}\rfloor=\lfloor B_{u}\rfloor$. In this
case, we discard the edge $(w,v)$: delete the edge $(w,v)$, delete the $+$
operation labeling the gate $v$, and contract the remaining edge $(u,v)$. If
$\mathrm{dg}(u)>\mathrm{dg}(w)$, then we discard the edge $(u,v)$.

A monotone Boolean function $f$ is _homogeneous_ if the set $A_{f}\subseteq
f^{-1}(1)$ of its lowest ones is homogeneous (meaning that all prime
implicants of $f$ have the same number of variables); note that then $\lfloor
A_{f}\rfloor=A_{f}$ holds. For a monotone Boolean function $f$, let

$\displaystyle\mathsf{B}^{\ast}_{k}(f):=$ min size of a monotone syntactically
read-$k$ $(\lor,\land)$ circuit computing $f$.

It is clear that $\mathsf{B}_{k}(f)\leqslant\mathsf{B}^{\ast}_{k}(f)$ always
holds.

######  Theorem 1.

For every monotone Boolean function $f$, we have

$\mathsf{Arith}(\lfloor
A_{f}\rfloor)\leqslant\mathsf{B}_{1}(f)\leqslant\mathsf{B}^{\ast}_{1}(f)\leqslant\mathsf{Arith}(A_{f})\,.$

In particular, if $f$ is homogeneous, then
$\mathsf{Arith}(A_{f})=\mathsf{B}_{1}(f)=\mathsf{B}^{\ast}_{1}(f)$.

###### Proof.

Let $A:=A_{f}\subseteq f^{-1}(1)$ be the set of the lowest ones of $f$; hence,
$f(x)=\bigvee_{a\in A}\bigwedge_{i\in\mathrm{sup}(a)}x_{i}$. To show the first
inequality $\mathsf{Arith}(\lfloor A\rfloor)\leqslant\mathsf{B}_{1}(f)$, let
$F$ be a monotone read-$1$ Boolean $(\lor,\land)$ circuit of size
$s=\mathsf{B}_{1}(f)$ computing $f$, and let $B\subseteq\mathbb{N}^{n}$ be the
set of “exponent” vectors produced by $F$. Consider the arithmetic
$(+,\times)$ version $F^{\prime}$ of $F$ obtained by replacing $\lor$-gates
with $+$ gates, and $\land$-gates with $\times$ gates. The arithmetic circuit
$F^{\prime}$ has the same number $s=\mathsf{B}_{1}(f)$ of gates. Since the
Boolean circuit $F$ is constant-free (by our assumption throughout the paper),
its arithmetic version $F^{\prime}$ is also constant-free. So, the circuit
$F^{\prime}$ produces a polynomial $P(x)=\sum_{b\in
B}c_{b}\prod_{i=1}^{n}x_{i}^{b_{i}}$ with the same set $B$ of exponent
vectors, and some integer coefficients $c_{b}\geqslant 1$. Since the
polynomial $P$ is similar to the polynomial $\sum_{b\in
B}\prod_{i=1}^{n}x_{i}^{b_{i}}$, we have $\mathsf{Arith}(B)\leqslant s$. By
Envelope Lemma, we have $\mathsf{Arith}(\lfloor
B\rfloor)\leqslant\mathsf{Arith}(B)\leqslant s$. So, it is enough to show that
$\lfloor A\rfloor=\lfloor B\rfloor$.

Since the (Boolean) circuit $F$ is a read-$1$ circuit, we know that the
inclusions $A\subseteq B\subseteq A^{\uparrow}$ hold. Let $m$ be the minimum
degree $|a|=a_{1}+\cdots+a_{n}$ of a vector $a\in A$; hence, $\lfloor
A\rfloor=\\{a\in A\colon|a|=m\\}$. The inclusion $B\subseteq A^{\uparrow}$
means that for every vector $b\in B$ there is a vector $a\in A$ such that
$b\geqslant a$. Together with the inclusion $A\subseteq B$, this implies that
$\lfloor B\rfloor=\\{b\in B\colon|b|=m\\}$ and $\lfloor
A\rfloor\subseteq\lfloor B\rfloor$. To show the inclusion $\lfloor
B\rfloor\subseteq\lfloor A\rfloor$, take an arbitrary vector $b\in\lfloor
B\rfloor$; hence, $|b|=m$. Since $B\subseteq A^{\uparrow}$, there must be a
vector $a\in A$ such that $b\geqslant a$. Since the set $A$ has no vectors of
degree $<m=|b|$, we have $b=a\in\lfloor A\rfloor$. Thus, $\lfloor
A\rfloor=\lfloor B\rfloor$ holds, as desired.

To show the inequality $\mathsf{B}^{\ast}_{1}(f)\leqslant\mathsf{Arith}(A)$,
let $F$ be a constant-free arithmetic $(+,\times)$ circuit of size
$s=\mathsf{Arith}(A)$ computing some polynomial $Q$ similar to
$P(x)=\sum_{a\in A}\prod_{i=1}^{n}x_{i}^{a_{i}}$. Thus, the set of exponent
vectors of the polynomial $Q$ is the same set $A=A_{f}$ as that of the
polynomial $P$. Let $F^{\prime}$ be the Boolean $(\lor,\land)$ version of $F$
obtained by replacing every $+$-gate with a $\lor$-gate, and every
$\times$-gate with a $\land$-gate. The resulting Boolean circuit $F^{\prime}$
produces the same set $A$ of exponent vectors as the arithmetic circuit $F$.
Hence, $F^{\prime}$ computes the Boolean version $f(x)=\bigvee_{a\in
A}\bigwedge_{i\in\mathrm{sup}(a)}x_{i}$ of the polynomial $P$. Since the set
$A=A_{f}$ of exponent vectors of $P$ consists of only $0$-$1$ vectors, the
circuit $F^{\prime}$ is a _syntactically_ read-$1$ circuit. Hence,
$\mathsf{B}^{\ast}_{1}(f)\leqslant s$, as desired.

###  5.1 An easy lower bound for monotone arithmetic circuits

The goal of this section is to demonstrate that strong lower bounds on the
size of monotone arithmetic $(+,\times)$ circuits and, hence (by Theorem 1),
also on the size of monotone Boolean read-$1$ $(\lor,\land)$ circuits can be
proved fairly easily.

The weakness of monotone arithmetic circuits lies in Fact 1: unlike for
monotone _Boolean_ circuits (where both idempotence $x\land x=x$ and
absorption $x\lor xy=x$ are allowed), monotone _arithmetic_ circuits “produce
what they compute.” This weakness results in the following “balanced
decomposition property” for arithmetic circuits computing homogeneous777A
polynomial $f(x)=\sum_{a\in A}c_{a}\prod_{i=1}^{n}x_{i}^{a_{i}}$ is monotone
if $c_{a}>0$ for all $a\in A$, and is _homogeneous_ of degree
$\mathrm{deg}(f)=m$ if $a_{1}+\cdots+a_{n}=m$ holds for all $a\in A$.
polynomials observed already by Hyafil [12, Theorem 1] and Valiant [47, Lemma
3].

######  Decomposition Lemma.

If a homogeneous polynomial $f$ of degree $m\geqslant 3$ can be computed by a
monotone arithmetic $(+,\times)$ circuit of size $s$, then $f$ can be written
as a sum $f=g_{1}h_{1}+\cdots+g_{t}h_{t}$ of $t\leqslant s$ products of
homogeneous polynomials such that $m/3\leqslant\mathrm{deg}(g_{i})\leqslant
2m/3$ for all $i=1,\ldots,t$.

In particular, the inclusions
$\mathrm{mon}(g_{i}h_{i})\subseteq\mathrm{mon}(f)$ hold for all
$i=1,\ldots,t$, where $\mathrm{mon}(f)$ denotes the set of all monomials of
$f$. That is every monomial of $g_{i}h_{i}$ must also be a monomial of the
computed polynomial (no “redundant” monomials can be produced); this is in
stark contrast with Boolean or tropical circuits, where nothing similar holds.
The proof of Decomposition Lemma is simple. If a circuit computes the
polynomial $f$, then (by Fact 1) it also produces that polynomial. Since $f$
is homogeneous, polynomials $g_{v}$ produced at intermediate gates $v$ are
also homogeneous. By walking backward from the output gate, and by always
choosing that of the two input gates $v$ with larger $\mathrm{deg}(g_{v})$, we
will find a gate $v$ with $m/3\leqslant\mathrm{deg}(g_{v})\leqslant 2m/3$.
Hence, the polynomial $f$ is of the form $f=g_{v}h_{v}+\cdots$ for some
polynomial $h_{v}$. Replace the gate $v$ by constant $0$, and argue by
induction on circuit size.

######  Example 2 (Perfect matchings).

The _perfect matching_ function is a monotone Boolean function
$\mathrm{Match}_{n}$ of $n^{2}$ variables, one for each edge of $K_{n,n}$,
such that $\mathrm{Match}_{n}(x)=1$ iff the subgraph of $K_{n,n}$ specified by
the input vector $x\in\\{0,1\\}^{n\times n}$ contains a perfect matching. We
will use the decomposition lemma to prove the following lower bound:

For $f=\mathrm{Match}_{n}$, we have
$\mathsf{B}_{1}(f)=\mathsf{Arith}(A_{f})=2^{\Omega(n)}$.

###### Proof.

The set $A_{f}$ of the lowest ones of this function consists of $|A_{f}|=n!$
characteristic $0$-$1$ vectors $a\in\\{0,1\\}^{n\times n}$ of all perfect
matchings (viewed as sets of their edges). Since the set $A_{f}$ is
homogeneous (of degree $n$), Theorem 1 yields
$\mathsf{B}_{1}(f)=\mathsf{Arith}(A_{f})$, and it remains to prove the lower
bound $\mathsf{Arith}(A_{f})=2^{\Omega(n)}$. The polynomial $\sum_{a\in
A_{f}}\prod_{i,j=1}^{n}x_{i,j}$ is the well known permanent polynomial
$\mathrm{Per}_{n}(x)=\sum_{\pi}\prod_{i=1}^{n}x_{i,\pi(i)}$, where the sum is
over all $n!$ permutations $\pi:[n]\to[n]$. Hence, $\mathsf{Arith}(A_{f})$ is
the minimum size $s$ of a monotone arithmetic circuit $F$ computing a
polynomial similar to the polynomial $\mathrm{Per}_{n}$.

To apply the decomposition lemma, take an arbitrary polynomial of the form
$gh$ with $\mathrm{mon}(gh)\subseteq\mathrm{mon}(\mathrm{Per}_{n})$ and
$\mathrm{deg}(g)=r$ for some $n/3\leqslant r\leqslant 2n/3$. Since the
polynomial $\mathrm{Per}_{n}$ is homogeneous of degree $n$, the polynomials
$g$ and $h$ must be homogeneous of degrees
$n/3\leqslant\mathrm{deg}(g)=r\leqslant 2n/3$ and
$n/3\leqslant\mathrm{deg}(h)=n-r\leqslant 2n/3$. Fix any two monomials
$p\in\mathrm{mon}(g)$ and $q\in\mathrm{mon}(h)$; hence, $p$ corresponds to a
matching in $K_{n,n}$ with $r$ edges, and $q$ corresponds to a matching in
$K_{n,n}$ with $n-r$ edges; since the polynomial $\mathrm{Per}_{n}$ is
multilinear, these two matchings must be vertex-disjoint. A matching in
$K_{n,n}$ with $r$ edges is contained in only $(n-r)!$ perfect matchings. So,
$|\mathrm{mon}(h)|=|\mathrm{mon}(p\cdot h)|\leqslant(n-r)!$ and
$|\mathrm{mon}(g)|=|\mathrm{mon}(g\cdot q)|\leqslant r!$. This gives an upper
bound $|\mathrm{mon}(gh)|=|\mathrm{mon}(g)|\cdot|\mathrm{mon}(h)|\leqslant
r!(n-r)!$ on the number of monomials in the polynomial $gh$. By Decomposition
Lemma, the circuit $F$ must have
$s\geqslant|\mathrm{mon}(f)|/|\mathrm{mon}(gh)|\geqslant
n!/r!(n-r)!=\binom{n}{r}$ gates. Since $\binom{n}{r}\geqslant\binom{n}{n/3}$
for every $n/3\leqslant r\leqslant 2n/3$, we have
$\mathsf{Arith}(A_{f})\geqslant\binom{n}{n/3}$.

######  Remark 4.

By using the permanent equivalent of Laplace’s expansion rule for
determinants, Jerrum and Snir [14] have shown that the permanent polynomial
$\mathrm{Per}_{n}$ (of $n^{2}$ variables) can be computed by a monotone
arithmetic $(+,\times)$ circuit using at most $t:=n(2^{n-1}-1)$ multiplication
$(\times)$ gates (using a more subtle argument as in the proof above, it is
proved in [14] that this number of multiplication gates is also necessarily.)
On the other hand, an argument similar to that used by Alon and Boppana [1,
Lemma 3.15] for monotone Boolean circuits implies that if a multilinear
$n$-variate polynomial $P$ can be computed by a monotone arithmetic
$(+,\times)$ circuit with $t$ multiplication $(\times)$ gates, then a
polynomial similar to $P$ can be computed by a monotone arithmetic
$(+,\times)$ circuit with $t$ multiplication $(\times)$ gates and
$\text{O}(tn+t^{2})$ addition $(+)$ gates. Thus, the minimum size of a
monotone arithmetic $(+,\times)$ circuit computing $\mathrm{Per}_{n}$ is
$2^{\Theta(n)}$.

##  6 From Tropical (min,+) to Boolean Read-$1$

A tropical $(\min,+)$ circuit is a circuit over the tropical semiring
$(R,\oplus,\odot)$ with $x\oplus y:=\min\\{x,y\\}$ and $x\odot y:=x+y$
(arithmetic addition); the domain is the set
$R=\mathbb{R}_{\mbox{\footnotesize$+$}}$ of all nonnegative real numbers.

Note that in the tropical $(\min,+)$ semiring, powering
$x_{i}^{a_{i}}=x_{i}\odot x_{i}\odot\cdots\odot x_{i}$ ($a_{i}\in\mathbb{N}$
times) turns into multiplication by scalars
$a_{i}x_{i}=x_{i}+x_{i}+\cdots+x_{i}$. So, a (generic) monomial
$\prod_{i=1}^{n}x_{i}^{a_{i}}$ turns into the tropical “monomial” $\langle
a,x\rangle=a_{1}x_{1}+\cdots+a_{n}x_{n}$, the scalar product of vectors $a$
and $x$, and a polynomial $\sum_{a\in A}c_{a}\prod_{i=1}^{n}x_{i}^{a_{i}}$
turns into the _tropical_ $(\min,+)$ polynomial $f(x)=\min_{a\in A}\langle
a,x\rangle+c_{a}$ with “exponent” vectors $a\in A$ and “coefficients”
$c_{a}\in\mathbb{R}_{+}$; vectors $a\in A$ are usually called _feasible
solutions_ of the corresponding minimization problem. For example, an
arithmetic polynomial $P(x,y)=2x^{3}y+4xy^{2}$ turns into the tropical
polynomial $f(x,y)=\min\\{3x+y+2,x+2y+4\\}$

A $(\min,+)$ circuit $F$ _approximates_ a given minimization problem
$f:\mathbb{R}_{\mbox{\footnotesize$+$}}^{n}\to\mathbb{R}_{\mbox{\footnotesize$+$}}$
within a factor $k\geqslant 1$ if for every input weighting
$x\in\mathbb{R}_{\mbox{\footnotesize$+$}}^{n}$, the inequalities
$f(x)\leqslant F(x)\leqslant k\cdot f(x)$ hold. That is, the circuit is not
allowed to output any better (smaller) than optimal values but is allowed to
output up to $k$ times worse than the optimal values. In particular, the
circuit $F$ _solves_ the problem $f$ exactly (approximates $f$ within factor
$k=1$) if $F(x)=f(x)$ holds for all
$x\in\mathbb{R}_{\mbox{\footnotesize$+$}}^{n}$.

The minimization problem
$f:\mathbb{R}_{\mbox{\footnotesize$+$}}^{n}\to\mathbb{R}_{\mbox{\footnotesize$+$}}$
represented by a tropical polynomial $f(x)=\min_{a\in A}\langle
a,x\rangle+c_{a}$ is _constant-free_ if $c_{a}=0$ for all $a\in A$.
Combinatorial optimization problems are usually constant-free. For example, in
the famous _MST problem_ (minimum weight spanning tree problem) on a given
graph $G$, the goal is to compute the constant-free $(\min,+)$ polynomial
$f(x)=\min_{a\in A}\langle a,x\rangle$, where $A$ is the set of characteristic
$0$-$1$ vectors of spanning trees of $G$ (viewed as sets of their edges). In
the not less prominent _assignment problem_ , $A$ is the set of characteristic
$0$-$1$ vectors of perfect matchings, etc.

Since constant inputs in $(\min,+)$ circuits can only affect the
“coefficients” $c_{a}$, such inputs “should” be of little use when solving
constant-free minimization problems. This intuition was confirmed in [18,
Lemma 3.2] using a simple argument (which we include for completeness): when
dealing with tropical $(\min,+)$ circuits approximating constant-free
minimization problems, we can safely restrict ourselves to constant-free
circuits. The _constant-free version_ of a $(\min,+)$ circuit $F$ is obtained
by replacing all constant inputs with constant $0$.

######  Lemma 3.

If a $(\min,+)$ circuit $F$ approximates a constant-free minimization problem
within a factor $k\geqslant 1$, then the constant-free version of $F$ also
approximates this problem within the same factor.

###### Proof.

Let $f(x)=\min_{a\in A}\langle a,x\rangle$ be a (constant-free) minimization
problem approximated by the circuit $F$ within factor $k$, and let
$g(x)=\min_{b\in B}\ \langle x,b\rangle+c_{b}$ be the tropical $(\min,+)$
polynomial produced by $F$. Since constant inputs can only affect the
“coefficients” $c_{b}$, the polynomial produced by the constant-free version
${F}^{o}$ of $F$ is the constant-free version ${g}^{o}(x)=\min_{b\in B}\
\langle x,b\rangle$ of the polynomial $g(x)$. Since the circuit $F$
approximates $f$ within the factor $k\geqslant 1$, the inequalities
$f(x)\leqslant g(x)\leqslant k\cdot f(x)$ hold for all weightings
$x\in\mathbb{R}_{\mbox{\footnotesize$+$}}^{n}$. We have to show that
$f(x)\leqslant{g}^{o}(x)\leqslant k\cdot f(x)$ also holds for all
$x\in\mathbb{R}_{\mbox{\footnotesize$+$}}^{n}$. Since the constants $c_{b}$
are nonnegative, we have ${g}^{o}(x)\leqslant g(x)\leqslant k\cdot f(x)$ for
all $x\in\mathbb{R}_{\mbox{\footnotesize$+$}}^{n}$. To show that
$f(x)\leqslant{g}^{o}(x)$ holds as well, suppose for the sake of contradiction
that $f(x_{0})>{g}^{o}(x_{0})$ holds for some input weighting
$x_{0}\in\mathbb{R}_{\mbox{\footnotesize$+$}}^{n}$. Then the difference
$d=f(x_{0})-{g}^{o}(x_{0})$ is positive. We can assume that the constant
$c:=\max_{b\in B}c_{b}$ is also positive, for otherwise, there would be
nothing to prove. So the constant $\lambda:=2c/d$ is positive. Since
${g}^{o}(x_{0})=f(x_{0})-d$, we obtain $g(\lambda
x_{0})\leqslant{g}^{o}(\lambda
x_{0})+c=\lambda\cdot{g}^{o}(x_{0})+c=\lambda[f(x_{0})-d]+c=\lambda\cdot
f(x_{0})-c=f(\lambda x_{0})-c$, which is strictly smaller than $f(\lambda
x_{0})$, a contradiction with $f(x)\leqslant g(x)$ for all
$x\in\mathbb{R}_{\mbox{\footnotesize$+$}}^{n}$.

If a tropical $(\min,+)$ circuit $F$ solves the minimization problem
$f_{A}(x)=\min_{a\in A}\ \langle a,x\rangle$ on a given set $A$ of feasible
solutions, then the set $B_{F}\subseteq\mathbb{N}^{n}$ of “exponent” vectors
does not need to coincide with $A$. For example, the circuit
$F=\min\\{x,y\\}+\min\\{x,y\\}$ solves the minimization problem
$f_{A}=\min\\{2x,2y\\}$ on $A=\\{(2,0),(0,2)\\}$ by producing the set
$B_{F}=\\{(2,0),(1,1),(0,2)\\}$ of “exponent” vectors. Note that the vector
$(1,1)$ is the convex combination $\tfrac{1}{2}(2,0)+\tfrac{1}{2}(0,1)$ of the
vectors of $A$.

And indeed, using a version of Farkas’ lemma, Jerrum and Snir [14] have shown
that the structures of the sets $A$ and $B_{F}$ are related via convexity.
Namely, a $(\min,+)$ circuit $F$ solves the minimization problem $f_{A}$ of a
set $A\subseteq\mathbb{N}^{n}$ of feasible solutions if and only if every
vector of $A$ contains888A vector $x\in\mathbb{R}^{n}$ _contains_ a vector
$y\in\mathbb{R}^{n}$ if $x\geqslant y$ holds, that is, if $x_{i}\geqslant
y_{i}$ for all $i=1,\ldots,n$. some convex combination of vectors in $B_{F}$,
and every vector of $B_{F}$ contains some convex combination of vectors in
$A$. The “if” direction here is simple: the scalar product of
$x\in\mathbb{R}^{n}$ with a convex combination of some collection of vectors
is at least the minimum scalar product of $x\in\mathbb{R}^{n}$ with some of
these vectors. The Farkas lemma is used in [14] to show the “only if”
direction.

In the case of $0$-$1$ optimization, feasible solutions $a\in A$ are $0$-$1$
vectors. In this case, the following properties of sets $B_{F}$ can be easily
proved without any use of Farkas’ lemma.

######  Lemma 4 (Structure).

Let $F$ be a constant-free $(\min,+)$ circuit, and
$B_{F}\subseteq\mathbb{N}^{n}$ be the set of “exponent” vectors produced by
$F$. If the circuit $F$ approximates the minimization problem
$f_{A}(x)=\min_{a\in A}\langle a,x\rangle$ on an antichain
$A\subseteq\\{0,1\\}^{n}$ within a factor $k\geqslant 1$, then $B_{F}\subseteq
A^{\uparrow}$ and for every vector $a\in A$ there is a vector $b\in B_{F}$
such that $\mathrm{sup}(b)=\mathrm{sup}(a)$ and $\langle a,b\rangle\leqslant
k\cdot\langle a,a\rangle$. In particular, if $k=1$, then $A\subseteq
B_{F}\subseteq A^{\uparrow}$.

###### Proof.

Let $B:=B_{F}$. Since the circuit $F$ is constant-free, the problem solved by
$F$ is of the form $f_{B}(x)=\min_{b\in B}\langle b,x\rangle$. Since $F$
approximates the problem $f_{A}$ within the factor $k$, inequalities
$f_{A}(x)\leqslant f_{B}(x)\leqslant k\cdot f_{A}(x)$ hold for all
$x\in\mathbb{R}_{\mbox{\footnotesize$+$}}^{n}$. To show the inclusion
$B\subseteq A^{\uparrow}$, take an arbitrary vector $b\in B$, and consider the
weighting $x\in\\{0,1\\}^{n}$ such that $x_{i}:=0$ for $i\in\mathrm{sup}(b)$,
and $x_{i}:=1$ for $i\not\in\mathrm{sup}(b)$. Take a vector $a\in A$ on which
the minimum $f_{A}(x)=\langle a,x\rangle$ is achieved. Then $\langle
a,x\rangle=f_{A}(x)\leqslant f_{B}(x)\leqslant\langle b,x\rangle=0$. Thus,
$\mathrm{sup}(a)\subseteq\mathrm{sup}(b)$. Since $b\in\mathbb{N}^{n}$ and $a$
is a $0$-$1$ vector, this yields $a\leqslant b$, as desired.

Now take an arbitrary vector $a\in$A, and consider the weighting
$x\in\\{1,kn+1\\}^{n}$ with $x_{i}:=1$ for all $i\in\mathrm{sup}(a)$ and
$x_{i}:=kn+1$ for all $i\not\in\mathrm{sup}(a)$. Let $b\in B$ be a vector on
which the minimum $f_{B}(x)=\langle b,x\rangle$ is achieved. Then $\langle
b,x\rangle=f_{B}(x)\leqslant k\cdot f_{A}(x)\leqslant k\cdot\langle
a,x\rangle=k\cdot\langle a,a\rangle\leqslant kn$. If $b_{i}\neq 0$ held for
some $i\not\in\mathrm{sup}(a)$, then we would have $\langle
b,x\rangle\geqslant b_{i}x_{i}=b_{i}(kn+1)>kn$, a contradiction. Thus, the
inclusion $\mathrm{sup}(b)\subseteq\mathrm{sup}(a)$ holds. Since $B\subseteq
A^{\uparrow}$, there is a vector $a^{\prime}\in A$ such that
$a^{\prime}\leqslant b$. Hence,
$\mathrm{sup}(a^{\prime})\subseteq\mathrm{sup}(b)\subseteq\mathrm{sup}(a)$.
Since both $a$ and $a^{\prime}$ are $0$-$1$ vectors, this yields
$a^{\prime}\leqslant a$ and, since the set $A$ is an antichain, we have
$a^{\prime}=a$ and, hence, also $\mathrm{sup}(b)=\mathrm{sup}(a)$. By the
definition of the weighting $x$, this yields $\langle a,b\rangle=\langle
b,x\rangle=f_{B}(x)\leqslant k\cdot\langle a,a\rangle$, as desired.

For a finite set $A\subseteq\mathbb{N}^{n}$ of vectors, let

$\displaystyle\mathsf{Min}_{k}(A):=$ smallest size of a $(\min,+)$ circuit
approximating the minimization problem $g(x)=\min_{a\in A}\langle a,x\rangle$
on $A$ within the factor $k$.

######  Theorem 2.

Let $f$ be a monotone Boolean function, $m$ be the largest number of variables
in a prime implicant of $f$, $k\geqslant 1$ be an integer, and $r=(k-1)m+1$.
Then

$\mathsf{B}_{r}(f)\leqslant\mathsf{Min}_{k}(A_{f})\leqslant\mathsf{B}_{k}(f)\,.$

In particular, $\mathsf{Min}_{1}(A_{f})=\mathsf{B}_{1}(f)$.

###### Proof.

Let $A:=A_{f}\subseteq\\{0,1\\}^{n}$ be the set of the lowest ones of $f$. To
show the inequality $\mathsf{Min}_{k}(A)\leqslant\mathsf{B}_{k}(f)$, let $F$
be a read-$k$ $(\lor,\land)$ circuit of size $\mathsf{B}_{k}(f)$ computing
$f$, and let $B:=B_{F}\subseteq\mathbb{N}^{n}$ be the set of “exponent”
vectors produced by $F$. The tropical $(\min,+)$ version $F^{\prime}$ of $F$
is a constant-free $(\min,+)$ circuit obtained by replacing $\lor$ gates with
$\min$ gates, and $\land$ gates with addition gates. That is, we (again)
replace “addition” gates by “addition” gates, and “multiplication” gates by
“multiplication” gates of the corresponding semirings. The circuit
$F^{\prime}$ produces the same set $B$ of “exponent” vectors. Hence, the
circuit $F^{\prime}$ solves the minimization problem $g_{B}(x)=\min_{b\in
B}\langle b,x\rangle$ on the set $B$. The minimization problem on the given
set $A$ is $g_{A}(x)=\min_{a\in A}\langle a,x\rangle$. It thus remains to show
that for every input weighting $x\in\mathbb{R}_{\mbox{\footnotesize$+$}}^{n}$
the inequalities $g_{A}(x)\leqslant g_{B}(x)\leqslant k\cdot g_{A}(x)$ hold.
So, take an arbitrary input weighting
$x\in\mathbb{R}_{\mbox{\footnotesize$+$}}^{n}$.

Since the Boolean circuit $F$ computes $f$, Lemma 1 gives us the inclusion
$B\subseteq A^{\uparrow}$, that is, for every vector $b\in B$ there is a
vector $a\in A$ such that $b\geqslant a$. Since the weights are nonnegative,
this gives the first inequality $g_{A}(x)\leqslant g_{B}(x)$. To show the
second inequality $g_{B}(x)\leqslant k\cdot g_{A}(x)$, take a vector $a\in A$
on which the minimum $g_{A}(x)=\langle a,x\rangle$ on the input weighting
$x\in\mathbb{R}_{\mbox{\footnotesize$+$}}^{n}$ is achieved, and let
$S:=\mathrm{sup}(a)$ be the support of $a$. Since $F$ is a read-$k$ circuit,
there is a vector $b\in B$ such that $\mathrm{sup}(b)=S$ and $b_{i}\leqslant
k$ for all $i\in S$. Thus, $g_{B}(x)\leqslant\langle b,x\rangle=\sum_{i\in
S}b_{i}x_{i}\leqslant k\cdot\sum_{i\in S}x_{i}=k\cdot\langle a,x\rangle=k\cdot
g_{A}(x)$, as desired.

To show the inequality, $\mathsf{B}_{r}(f)\leqslant\mathsf{Min}_{k}(A)$ take a
tropical $(\min,+)$ circuit $F$ of size $\mathsf{Min}_{k}(A)$ approximating
the (constant-free) minimization problem $g_{A}(x)=\min_{a\in A}\langle
a,x\rangle$ within the factor $k$, and let $B:=B_{F}\subseteq\mathbb{N}^{n}$
be the set of “exponent” vectors produced by the circuit $F$. By Lemma 3, we
can assume that the circuit $F$ is constant-free, that is, has no nonzero
constant inputs. So, the polynomial $g_{B}(x)=\min_{b\in B}\langle b,x\rangle$
produced by $F$ is also constant-free. The Boolean $(\lor,\land)$ version
$F^{\prime}$ of $F$ (obtained by replacing $\min$ gates with $\lor$ gates, and
addition gates with $\land$ gates) produces the same set $B$ of “exponent”
vectors. Since the $(\min,+)$ circuit $F$ approximates the problem $g_{A}$
within the factor $k$, Lemma 4 implies that the set $B$ has the following two
properties: (i) $B\subseteq A^{\uparrow}$, and (ii) for every vector $a\in A$
there is a vector $b\in B$ such that $\mathrm{sup}(b)=\mathrm{sup}(a)$ and
$\langle a,b\rangle\leqslant k\cdot\langle a,a\rangle$. This, in particular,
yields the inclusion $\mathrm{Sup}(A)\subseteq\mathrm{Sup}(B)$. Together with
$B\subseteq A^{\uparrow}$, Lemma 1 implies that the $(\lor,\land)$ circuit
$F^{\prime}$ computes our Boolean function $f$, and it remains to show that
$F^{\prime}$ is a read-$r$ circuit for $r:=(k-1)m+1$.

To show this, take an arbitrary lowest one $a\in A$ of $f$, and let
$S:=\mathrm{sup}(a)$ be its support; hence, $|S|\leqslant m$. By property
(ii), there is a vector $b\in B$ such that $\mathrm{sup}(b)=S$ and $\sum_{i\in
S}b_{i}\leqslant k|S|$. It remains to show that the vector $b$ is $r$-bounded.
Suppose for the sake of contradiction that $b_{j}\geqslant r+1=(k-1)m+2$ holds
for some position $j\in S$. Since $b_{i}\geqslant 1$ holds for all $i\in S$,
we then have $\sum_{i\in S}b_{i}\geqslant
r+1+(|S|-1)=(k-1)m+2+(|S|-1)\geqslant(k-1)|S|+2+(|S|-1)=k|S|+1$, a
contradiction with $\sum_{i\in S}b_{i}\leqslant k|S|$.

##  7 From Non-Monotone Multilinear to Monotone Read-1

Due to the lack of strong lower bounds for (non-monotone) arithmetic
$(+,\times,-)$ circuits, and because they seem to be the most intuitive
circuits for computing _multilinear_ polynomials, a successful approach has
been to consider a restriction called “multilinearity” of arithmetic circuits,
first introduced by Nisan and Wigderson [28].

Recall that a polynomial is multilinear if it does not have any variable with
degree larger than $1$. An arithmetic $(+,\times,-)$ circuit $F$ is
_syntactically multilinear_ if the two subcircuits rooted at inputs of any
multiplication $(\times)$ gate have no input variables in common. The circuits
$F$ is (semantically) _multilinear_ if the polynomial _functions_ computed at
its gates polynomials are multilinear. For example, the polynomial function
$f=y$ computed at a gate producing the polynomial $P=x^{2}+y-x^{2}$ is
multilinear. Raz [32, Proposition 2.1] observed that minimal semantically
multilinear $(+,\times,-)$ _formulas_ (circuits whose underlying graphs are
trees) are syntactically multilinear. It remains not clear if every
semantically multilinear _circuit_ can be efficiently simulated by a
syntactically multilinear circuit.

There are several impressing results concerning multilinear (as well as
syntactically multilinear) arithmetic $(+,\times,-)$ circuits and formulas;
see, for example, the surveys [6, 42]. In particular, Raz [32] proved that any
multilinear arithmetic _formula_ computing the permanent or the determinant of
an $n\times n$ matrix is of size $n^{\Omega(\log n)}$. Furthermore, Raz [31]
proved that a gap between multilinear arithmetic _formulas_ and _circuits_ can
be super-polynomial. Proving super-polynomial lower bounds of the size of
multilinear arithmetic _circuits_ remains an open problem.

Due to the lack of even super-linear lower bounds on the size of
(unrestricted) DeMorgan $(\lor,\land,\neg)$ circuits, and by analogy with
arithmetic circuits, the multilinearity restriction was also imposed on
DeMorgan circuits. Recall that a DeMorgan $(\lor,\land,\neg)$ circuit999Let us
note that every Boolean $(\lor,\land,\neg)$ circuit (with negations applied to
any gates, not necessarily to only inputs) can be easily transformed into an
equivalent DeMorgan $(\lor,\land,\neg)$ circuit by only doubling the circuit
size (see, e.g., [48, p. 195]): we double all AND and OR gates, one output of
a pair is negated, the other one not; after that, we can move negation gates
toward the input variables by applying the DeMorgan rules. $F$ is an
$(\lor,\land)$ circuit whose inputs are the variables $x_{1},\ldots,x_{n}$ and
their negations $\overline{x}_{1},\ldots,\overline{x}_{n}$. As before, the
_size_ of a circuit is the total number of gates in it. A _monotone_ Boolean
circuit is a DeMorgan circuit without negated input literals as inputs.

A DeMorgan $(\lor,\land,\neg)$ circuit $F$ is _syntactically multilinear_ if
the two subcircuits rooted at inputs of any AND gate have no input literals of
the same variable in common. For example, the circuit $F=(x\lor
x\overline{y})y$ is _not_ syntactically multilinear. Sengupta and
Venkateswaran [39] considered the _connectivity_ function which accepts an
input $x\in\\{0,1\\}^{\binom{n}{2}}$ iff the subgraph $G_{x}$ of $K_{n}$
specified by the characteristic $0$-$1$ vector $x$ of its set of edges is
connected. By adopting the proof of Jerrum and Snir [14] of a lower bound
$(4/3)^{n-1}/n$ on the minimum size of monotone arithmetic $(+,\times)$
circuits computing the directed spanning tree polynomial, it was shown in [39]
that every monotone syntactically multilinear $(\lor,\land)$ circuit computing
the connectivity function must have at least $\sqrt{(4/3)^{n-1}/n}$ gates.

Krieger [21] has shown that if the set $A_{f}$ of the lowest ones of a
monotone Boolean function $f$ is cover-free (that is, if $a,b,c\in A_{f}$ and
$a+b\geqslant c$ imply $c\in\\{a,b\\}$), then every syntactically multilinear
DeMorgan $(\lor,\land,\neg)$ circuit computing $f$ must have at least
$|A_{f}|-1$ gates.

######  Remark 5.

As mentioned in Section 5.1, already in 1976, Schnorr [38] has proved a
general lower bound $\mathsf{Arith}(A)\geqslant|A|-1$ on the monotone
_arithmetic_ circuit complexity of polynomials, whose sets
$A\subseteq\mathbb{N}^{n}$ of exponent vector are cover-free. This surprising
similarity of Krieger’s bound in [21] with Schnorr’s bound, as well as a
possibility to adopt in [39] the argument of Jerrum and Snir, already served
as an indication that there “should” be some _general_ relation between
multilinear DeMorgan $(\lor,\land,\neg)$ circuits and monotone arithmetic
circuits. Our Theorems 3 and 4 below give such a relation, even for
semantically (not only syntactically) multilinear DeMorgan $(\lor,\land,\neg)$
circuits: such circuits are _not_ stronger than monotone arithmetic circuits.

Following the analogy with arithmetic circuits, Ponnuswami and Venkateswaran
[30] relaxed the _syntactic_ multilinearity restriction of Boolean circuits to
their _semantic_ multilinearity. A Boolean function $f(x_{1},\ldots,x_{n})$
_depends_ on the $i$th variable $x_{i}$ if $f(a)\neq f(b)$ holds for some two
vectors $a,b\in\\{0,1\\}^{n}$ that differ only in the $i$th position. The
following simple fact is well known; see, for example, [7, Theorem 1.17].

######  Fact 2 (Folklore).

A Boolean function $f(x_{1},\ldots,x_{n})$ depends on the $i$th variable
$x_{i}$ iff $x_{i}$ or $\overline{x}_{i}$ appears in at least one prime
implicant of $f$.

###### Proof.

The “only if” direction follows from the obvious fact that every Boolean
function $f$ is an OR of its prime implicants. So, if neither $x_{i}$ nor
$\overline{x}_{i}$ appears in any prime implicant of $f$, then $f$ does not
depend on the $i$th variable. To show the “if” direction, let $t=zt^{\prime}$
be a prime implicant of $f$, where $z\in\\{x_{i},\overline{x}_{i}\\}$. Since
the implicant $t$ is prime, the term $t^{\prime}$ is not an implicant of $f$.
That is, there is a vector $a\in\\{0,1\\}^{n}$ such that $t^{\prime}(a)=1$ but
$f(a)=0$ and, hence, also $t(a)=0$ (because $t\leqslant f$). Let $b$ be the
vector $a$ with its $i$th bit $a_{i}$ replaced by $1-a_{i}$. Then $t(b)=1$
and, hence, also $f(b)=1$, meaning that the function $f$ depends on the $i$th
variable.

Say that two Boolean functions are _independent_ if they depend on disjoint
sets of variables.

######  Definition 3 (Multilinear circuits).

A DeMorgan $(\lor,\land,\neg)$ circuit $F$ is _multilinear_ (or _semantically
multilinear_) if the two Boolean functions $g$ and $h$ computed at the inputs
to any AND gate are independent.

By Fact 2, the functions $g$ and $h$ are independent iff their prime
implicants share no common variables (negated or not). However, the terms
actually _produced_ at the gates _computing_ these functions _can_ share
common variables. This explains the use of the adjective “semantically.” For
example, the circuit $F=(x\lor xy)(\overline{y}\lor\overline{y}z)$ is not
syntactically multilinear, but is (semantically) multilinear because $g=x\lor
xy$ depends only on $x$, while $h=\overline{y}\lor\overline{y}z$ depends only
on $y$.

The _upward closure_ of a Boolean function $f:\\{0,1\\}^{n}\to\\{0,1\\}$ is
the monotone Boolean function

$f^{\triangledown}(x):=\bigvee_{z\leqslant x}f(z)\,.$

For example, the upward closure of the parity function $f=x_{1}\oplus
x_{2}\oplus\cdots\oplus x_{n}$ is $f^{\triangledown}=x_{1}\lor
x_{2}\lor\cdots\lor x_{n}$. Note that $f^{\triangledown}=f$ holds for
_monotone_ functions $f$. Also note that $(g\lor
h)^{\triangledown}=g^{\triangledown}\lor h^{\triangledown}$ holds for any
Boolean functions $g,h:\\{0,1\\}^{n}\to\\{0,1\\}$. Thus, if $\mathrm{PI}(f)$
is the set of all prime implicants of a Boolean function
$f:\\{0,1\\}^{n}\to\\{0,1\\}$, then

$f^{\triangledown}=\big{(}\bigvee_{t\in\mathrm{PI}(f)}t\big{)}^{\triangledown}=\bigvee_{t\in\mathrm{PI}(f)}t^{\triangledown}=\bigvee_{t\in\mathrm{PI}(f)}{t}^{+}\,,$

where ${t}^{+}$ is the _positive factor_ of a term $t$ obtained from $t$ by
replacing every negated literal $\overline{x}_{i}$ with constant $1$. Thus,
the upward closure $f^{\triangledown}$ of any Boolean function $f$ is the OR
of positive factors of prime implicants of $f$.

A _lowest one_ of a (not necessarily monotone) Boolean function
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ is a vector $a\in\\{0,1\\}^{n}$ such that
$f(a)=1$ but $f(b)=0$ for all $b<a$; for vectors $a,b\in\mathbb{R}^{n}$ we
write $b<a$ if $b\leqslant a$ and $b_{i}<a_{i}$ for at least one position $i$.
Let, as before, $A_{f}\subseteq f^{-1}(1)$ denote the set of all lowest ones
of $f$. For example, the set $\\{\vec{e}_{1},\ldots,\vec{e}_{n}\\}$ of $n$
unit vectors is the set of the lowest ones of $x_{1}\oplus
x_{2}\oplus\cdots\oplus x_{n}$ as well as of $x_{1}\lor x_{2}\lor\cdots\lor
x_{n}$. Note that, unlike for _monotone_ Boolean functions, $a\in A_{f}$ does
not exclude that $f(c)=0$ holds for some vectors $c\geqslant a$. For example,
$a=(1,0)$ is a lowest one of the function
$f=x\overline{y}\lor\overline{x}y=x\oplus y$, but $f(c)=0$ for $c=(1,1)$.

######  Remark 6.

It is easy to verify that the lowest ones of a function
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ and of its downward closure $f^{\triangledown}$
are the same, that is, $A_{f^{\triangledown}}=A_{f}$ holds. Indeed, if $a\in
A_{f}$, then $f(a)=1$ but $f(b)=0$ for all $b<a$. Hence, also
$A_{f^{\triangledown}}(a)=1$ but $A_{f^{\triangledown}}(b)=0$ for all $b<a$.
This shows the inclusion $A_{f}\subseteq A_{f^{\triangledown}}$. If $a\in
A_{f^{\triangledown}}$, then $A_{f^{\triangledown}}(a)=1$ but
$A_{f^{\triangledown}}(b)=0$ and, hence, also $f(b)=0$ holds for all $b<a$.
Since $f^{\triangledown}(a)=1$ still holds, this can happen only if $f(a)=1$.
Hence, the converse inclusion $A_{f^{\triangledown}}\subseteq A_{f}$ also
holds.

For a Boolean function $f$, let $\mathsf{B}_{\mathrm{lin}}(f)$ denote the
minimum size of a (semantically) multilinear DeMorgan $(\lor,\land,\neg)$
circuit computing $f$. For a _monotone_ Boolean function $f$, let
$\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f)$ denote the minimum
size of a _monotone_ (semantically) multilinear $(\lor,\land)$ circuit
computing $f$. It is clear that
$\mathsf{B}_{\mathrm{lin}}(f)\leqslant\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f)$
holds for every _monotone_ Boolean function $f$.

######  Theorem 3 (Arbitrary functions).

For every Boolean function $f$, we have

$\mathsf{Arith}(\lfloor
A_{f}\rfloor)\leqslant\mathsf{B}_{1}(f^{\triangledown})\leqslant\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f^{\triangledown})\leqslant\mathsf{B}_{\mathrm{lin}}(f)\,.$

We will actually prove slightly stronger results: (i) instead of just an
inequality
$\mathsf{B}_{1}(f^{\triangledown})\leqslant\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f^{\triangledown})$,
we shown that every multilinear _monotone_ $(\lor,\land)$ circuit _is_ a
read-$1$ circuit (Lemma 7), and (ii) instead of just an inequality
$\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f^{\triangledown})\leqslant\mathsf{B}_{\mathrm{lin}}(f)$,
we shown that if a multilinear DeMorgan $(\lor,\land,\neg)$ circuit $F$
computes a Boolean function $f$, then the monotone $(\lor,\land)$ circuit
${F}^{+}$, obtained from $F$ by replacing every negated input variable
$\overline{x}_{i}$ with constant $1$, is also multilinear and computes
$f^{\triangledown}$ (Lemma 6).

Let us first prove the following easy consequence of Theorem 3 for multilinear
$(\lor,\land,\neg)$ circuits computing _monotone_ Boolean functions $f$, and
then prove Theorem 3 itself.

######  Theorem 4 (Monotone functions).

For every monotone Boolean function $f$, we have

$\mathsf{Arith}(\lfloor
A_{f}\rfloor)\leqslant\mathsf{B}_{1}(f)\leqslant\mathsf{B}_{\mathrm{lin}}(f)=\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f)\leqslant\mathsf{Arith}(A_{f})\,.$

In particular, of $f$ is also homogeneous, then
$\mathsf{Arith}(A_{f})=\mathsf{B}_{1}(f)=\mathsf{B}_{\mathrm{lin}}(f)=\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f)$.

###### Proof.

The inequality $\mathsf{Arith}(\lfloor
A_{f}\rfloor)\leqslant\mathsf{B}_{1}(f)$ is given by Theorem 1. Since $f$ is
monotone, we have $f^{\triangledown}=f$. So, the equality
$\mathsf{B}_{\mathrm{lin}}(f)=\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f)$
follows from a trivial upper bound
$\mathsf{B}_{\mathrm{lin}}(f)\leqslant\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f)$
and from the lower bound
$\mathsf{B}_{\mathrm{lin}}(f)\geqslant\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f^{\triangledown})=\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f)$
given by Theorem 3. It therefore remains to prove the upper bound
$\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f)\leqslant\mathsf{Arith}(A_{f})$.

For this, let $A:=A_{f}$ be the set of the lowest ones of $f$, and take a
monotone arithmetic constant-free $(+,\times)$ circuit $F$ of size
$s=\mathsf{Arith}(A)$ computing some polynomial $P(x)=\sum_{a\in
A}c_{a}\prod_{i=1}^{n}x_{i}^{a_{i}}$ similar to $\sum_{a\in
A}\prod_{i=1}^{n}x_{i}^{a_{i}}$. By Fact 1, the circuit $F$ also _produces_
the polynomial $P$. Let $F^{\prime}$ be the Boolean $(\lor,\land)$ version of
the circuit $F$ obtained by replacing each $+$-gate by a $\lor$-gate, and each
$\times$-gate by $\land$-gate. The circuit $F^{\prime}$ produces the same set
$A$ of exponent vectors and, hence, computes our Boolean function
$f(x)=\bigvee_{a\in A}\bigwedge_{i\in\mathrm{sup}(a)}x_{i}$. Since $A$
consists of only $0$-$1$ vectors, the polynomial $P$ produced by the
arithmetic circuit $F$ is multilinear, meaning that the polynomials produced
at inputs of any multiplication gate cannot share any variables in common.
Thus, the Boolean version $F^{\prime}$ of $F$ is (even syntactically)
multilinear.

######  Remark 7.

Ponnuswami and Venkateswaran [30] proved a lower bound
$\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f)=\Omega(2^{.459n})$ for
the perfect matching function $f=\mathrm{Match}_{n}$ (which we considered in
Section 5.1). On the other hand, using arguments tighter than we used in
Example 2, Jerrum and Snir [14] have proved a lower bound
$\mathsf{Arith}(A_{f})\geqslant n(2^{n-1}-1)$ for $f$. The function $f$ is
homogeneous (each prime implicant has $n$ variables). So, by Theorem 4, the
same lower bound $\mathsf{B}_{\mathrm{lin}}(f)\geqslant n(2^{n-1}-1)$ holds
even for non-monotone circuits.

######  Remark 8.

Lingas [24] has proved a lower bound
$\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f)\geqslant\mathsf{Arith}(A_{f})/\text{O}(m^{2})$
for every monotone homogeneous Boolean function, where $m$ is the number of
variables in the prime implicants of $f$. On the other hand, Theorem 4 shows
that, for homogeneous monotone functions $f$, we actually have the equality
$\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f)=\mathsf{Arith}(A_{f})$,
and even the equality $\mathsf{B}_{\mathrm{lin}}(f)=\mathsf{Arith}(A_{f})$.
That is, multilinear (not necessarily monotone) DeMorgan $(\lor,\land,\neg)$
circuits computing monotone homogeneous Boolean functions have the _same_
power as monotone arithmetic constant-free $(+,\times)$ circuits.

###  7.1 Proof of Theorem 3

Since lowest ones of a Boolean function $f$ and of its upward closure
$g:=f^{\triangledown}$ are the same (see Remark 6), we have $\lfloor
A_{f}\rfloor=\lfloor A_{g}\rfloor$. By Theorem 1, $\mathsf{Arith}(\lfloor
A_{f}\rfloor)=\mathsf{Arith}(\lfloor A_{g}\rfloor)\leqslant\mathsf{B}_{1}(g)$.
This shows the first inequality in Theorem 3. To prove the remaining two
inequalities of Theorem 3, we first establish (in Lemma 5) the behavior of
sets of lowest ones as well as of upward closures of functions computed at the
gates of DeMorgan $(\lor,\land,\neg)$ circuits. When doing this, we will use
the following simple property of independent Boolean functions following from
Fact 2. For $0$-$1$ vectors $a,b\in\\{0,1\\}^{n}$, $a\lor b\in\\{0,1\\}^{n}$
denotes their componentwise OR. For example, if $a=(1,1,0)$ and $b=(0,1,1)$
then $a+b=(1,2,1)$ but $a\lor b=(1,1,1)$.

######  Fact 3.

Let $g,h:\\{0,1\\}^{n}\to\\{0,1\\}$ be Boolean functions, and let $b\in A_{g}$
and $c\in A_{h}$ be their lowest ones. If $g$ and $h$ are independent, then
$\mathrm{sup}(b)\cap\mathrm{sup}(c)=\emptyset$ (hence, also $b\lor c=b+c$) and
$g(b\lor c)=h(b\lor c)=1$.

###### Proof.

Note that $t(b)=1$ holds for some prime implicant $t=\bigwedge_{i\in
S}x_{i}\land\bigwedge_{j\in T}\overline{x}_{j}$ of $g$ with
$S=\mathrm{sup}(b)$: we have $S\subseteq\mathrm{sup}(b)$ since $t(b)=1$, and
$\mathrm{sup}(b)\subseteq S$ since $g(b)=1$ and $b$ is a _lowest_ one of $g$.
So, since $g$ and $h$ are independent, the disjointness
$\mathrm{sup}(b)\cap\mathrm{sup}(c)=\emptyset$ follows from Fact 2. In
particular, $b+c=b\lor c$ is a $0$-$1$ vector. Since the function $g$ does not
depend on any variable $x_{i}$ with $i\in\mathrm{sup}(c)$, we have $g(b\lor
c)=g(b+c)=g(b+\vec{0})=g(b)=1$. Similarly, since function $h$ does not depend
on any variable $x_{i}$ with $i\in\mathrm{sup}(b)$, we also have $h(b\lor
c)=h(b+c)=h(\vec{0}+c)=h(c)=1$.

Recall that the Minkowski sum of two sets $A,B\subseteq\mathbb{R}^{n}$ is the
set $A+B=\\{a+b\colon a\in A,b\in B\\}$.

######  Lemma 5.

Let $g,h:\\{0,1\\}^{n}\to\\{0,1\\}$ be Boolean functions.

  * (i)

If $f=g\lor h$, then $A_{f}\subseteq A_{g}\cup A_{h}$ and
$f^{\triangledown}=g^{\triangledown}\lor h^{\triangledown}$.

  * (ii)

If $f=g\land h$ and $g,h$ are independent, then $A_{f}\subseteq A_{g}+A_{h}$
and $f^{\triangledown}=g^{\triangledown}\land h^{\triangledown}$.

###### Proof.

To show (i), let $f=g\lor h$. The inclusion $A_{f}\subseteq A_{g}\cup A_{h}$
is trivial: if $a\in A_{f}$, then $g(a)=1$ or $h(a)=1$, and both $g(b)=0$ and
$h(b)=0$ hold for every vector $b<a$. Thus, either $a\in A_{g}$ or $a\in
A_{h}$, as desired. To show the inequality $f^{\triangledown}\leqslant
g^{\triangledown}\lor h^{\triangledown}$, take any vector $x\in\\{0,1\\}^{n}$
for which $f^{\triangledown}(x)=1$ holds; hence, $x\geqslant a$ for some
lowest one $a\in A_{f}$. Then, as we have just shown, either $a\in A_{g}$ or
$a\in A_{h}$ (or both) hold. Hence, either $g^{\triangledown}(x)=1$ or
$h^{\triangledown}(x)=1$, as desired. To show the opposite inequality
$f^{\triangledown}\geqslant g^{\triangledown}\lor h^{\triangledown}$, take any
vector $x\in\\{0,1\\}^{n}$ for which $g^{\triangledown}(x)=1$ holds. Then
$g(z)=1$ and, hence, also $f(z)=1$ holds for some $z\leqslant x$, meaning that
$f^{\triangledown}(x)=1$, as desired. The same happens if
$h^{\triangledown}(x)=1$.

To show (ii), let $f=g\land h$, where the functions $g$ and $h$ are
independent. Take an arbitrary lowest one $a\in A_{f}$. Since then $g(a)=1$
and $h(a)=1$, there are lowest ones $b\in A_{g}$ and $c\in A_{h}$ such that
$b\leqslant a$ and $c\leqslant a$; hence, $a\geqslant b\lor c$. Since the
functions $g$ and $h$ are independent, Fact 3 yields $b\lor c=b+c$ and
$g(b+c)=h(b+c)=1$; hence, also $f(b+c)=1$. Since $a\geqslant b+c$ and since
vector $a$ is a _lowest_ one of $f$, this yields the equality $a=b+c$; hence,
$a\in A_{g}+A_{h}$. This shows the inclusion $A_{f}\subseteq A_{g}+A_{h}$.

The inequality $f^{\triangledown}\leqslant g^{\triangledown}\land
h^{\triangledown}$ is trivial and holds for arbitrary (not necessarily
independent) Boolean functions $g$ and $h$: if $f^{\triangledown}(x)=1$, then
$f(z)=1$ holds for some vector $z\leqslant x$ and, hence, both $g(z)=1$ and
$h(z)=1$ also hold. To show the converse inequality $g^{\triangledown}\land
h^{\triangledown}\leqslant f^{\triangledown}$ for independent functions $g$
and $h$, take any vector $x\in\\{0,1\\}^{n}$ for which both
$g^{\triangledown}(x)=1$ and $h^{\triangledown}(x)=1$ hold. Then $g(b)=1$ and
$h(c)=1$ hold for some lowest one $b\leqslant x$ of $g$ and for some lowest
one $c\leqslant x$ of $h$. Since the functions $g$ and $h$ are independent,
Fact 3 yields $g(b\lor c)=h(b\lor c)=1$ and, hence, also $f(b\lor c)=1$. Since
$b\lor c\leqslant x$, this yields $f^{\triangledown}(x)=1$, as desired.

######  Remark 9.

In general, if $f=g\land h$, and if the functions $g$ and $h$ are not
independent, then even the inclusion $A_{f}\subseteq A_{g}\lor A_{h}:=\\{b\lor
c\colon b\in A_{g},x\in A_{h}\\}$ does not need to hold. Take, for example,
$g=x\overline{y}\,\overline{z}\lor xy$ and $h=\overline{x}\,\overline{y}z\lor
yz$; hence, $f=xyz$. The functions $g$ and $h$ are dependent (their prime
implicants $xy$ and $yz$ share a common variable $y$). The only lowest one of
$f$ is $a=(1,1,1)$, the only lowest one of $g$ is $b=(1,0,0)$, and the only
lowest one of $h$ is $c=(0,0,1)$. But $a\neq b\lor c$. Also, in general, the
inequality $g^{\triangledown}\land h^{\triangledown}\leqslant
f^{\triangledown}$ does not need to hold. Take, for example,
$g=x\overline{y}\lor z$ and $h=\overline{x}y\lor z$; hence, $f=z$. On the
vector $a=(1,1,0)$, we have $f^{\triangledown}(a)=f(a)=0$, but
$g^{\triangledown}(a)\geqslant g(1,0,0)=1$ and $h^{\triangledown}(a)\geqslant
h(0,1,0)=1$.

We now turn to the actual proof of the remaining two inequalities
$\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f^{\triangledown})\leqslant\mathsf{B}_{\mathrm{lin}}(f)$
and
$\mathsf{B}_{1}(f^{\triangledown})\leqslant\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f^{\triangledown})$
claimed in Theorem 3. This is done in Lemmas 6 and 7 bellow.

We can view every DeMorgan $(\lor,\land,\neg)$ circuit $F(x)$ computing a
Boolean function $f(x)$ of $n$ variables as a _monotone_ $(\lor,\land)$
circuit $H(x,y)$ of $2n$ variables with the property that
$f(x)=H(x,\overline{x})$ holds for all $x\in\\{0,1\\}^{n}$, where
$\overline{x}=(\overline{x}_{1},\ldots,\overline{x}_{n})$ is the complement of
$x=(x_{1},\ldots,x_{n})$. For example, if $x=(1,0,1,1)$, then
$\overline{x}=(0,1,0,0)$. The _monotone version_ of the circuit $F(x)$ is the
monotone circuit ${F}^{+}(x)=H(x,\vec{1})$ obtained by replacing every negated
input literal $\overline{x}_{i}$ in the circuit $F$ with constant $1$.

Take, for example, the circuit $F=(x\overline{y}\lor z)(\overline{x}y\lor z)$
computing the Boolean function $f=z$. Its monotone version ${F}^{+}=(x\cdot
1\lor z)(1\cdot y\lor z)=(x\lor z)(y\lor z)$ computes the Boolean function
$xy\lor z$ which is _different_ from the upward closure $f^{\triangledown}=z$
of $f$. The following lemma shows that this cannot happen for _multilinear_
circuits $F$.

######  Lemma 6 (Multilinear to monotone multilinear).

Let $F$ be a DeMorgan $(\lor,\land,\neg)$ circuit computing a Boolean function
$f$. If $F$ is multilinear, then the circuit ${F}^{+}$ is also multilinear and
computes $f^{\triangledown}$. In particular,
$\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f^{\triangledown})\leqslant\mathsf{B}_{\mathrm{lin}}(f)$
holds.

###### Proof.

Suppose that the circuit $F(x)=H(x,\overline{x})$ is multilinear. To show that
the (monotone) circuit ${F}^{+}(x)=H(x,\vec{1})$ is multilinear, let $g$ and
$h$ be the Boolean functions computed at some AND gate of the circuit
$F(x)=H(x,\overline{x})$. Since the circuit $F(x)$ is multilinear, the
functions $g$ and $h$ are independent. By Fact 2, this happens precisely when
their prime implicants share no variables in common. Since the upward closure
of any Boolean function is the OR of positive factors of its prime implicants,
Fact 2 implies that the functions $g^{\triangledown}$ and $h^{\triangledown}$
are also independent.

Let us now show that the monotone version ${F}^{+}=H(x,\vec{1})$ of $F$
computes the upward closure $f^{\triangledown}$ of $f$. Upward closures of
input variables $x_{i}$ are the variables $x_{i}^{\triangledown}=x_{i}$
themselves, while upward closures of negated input variables
$\overline{x}_{i}$ are constant-$1$ functions
$\overline{x}_{i}^{\triangledown}=1$. Let $g$ and $h$ be the Boolean functions
computed at the two inputs of an arbitrary gate of $F$. If this is an OR gate,
then Lemma 5 yields the equality $(g\lor
h)^{\triangledown}=g^{\triangledown}\lor h^{\triangledown}$. If this is an AND
gate then, since the circuit $F$ is multilinear, the functions $g$ and $h$ are
independent, and Lemma 5 also yields the equality $(g\land
h)^{\triangledown}=g^{\triangledown}\land h^{\triangledown}$. Thus, in the
circuit ${F}^{+}=H(x,\vec{1})$, the upward closures $g^{\triangledown}$ of the
functions $g$ computed at the gates of $F$ are computed. Since this also holds
for the output gate of $F$, at which the function $f$ is computed, the upward
closure $f^{\triangledown}$ of $f$ is computed at this gate in the circuit
${F}^{+}$, as desired.

######  Lemma 7 (Monotone multilinear to read-$1$).

Monotone multilinear Boolean circuits are read-$1$ circuits. In particular,
$\mathsf{B}_{1}(f)\leqslant\mathsf{B}^{\mbox{\footnotesize$+$}}_{\mathrm{lin}}(f)$
holds for every monotone Boolean function $f$.

###### Proof.

Let $F$ be a monotone multilinear $(\lor,\land)$ circuit computing a monotone
Boolean function $f$. Let $B_{F}\subseteq\mathbb{N}^{n}$ be the set of
“exponent” vectors produced by $F$. By Lemma 1, the inclusion
$B_{F}\subseteq(A_{f})^{\uparrow}$ holds. So, to show that $F$ is a read-$1$
circuit, we have only to show that also the inclusion $A_{f}\subseteq B_{F}$
holds, i.e., that every lowest one $a\in A_{f}$ of $f$ is produced by the
circuit $F$.

Let $G$ and $H$ be the subcircuits of $F$ whose output gates enter the output
gate of $F$, and let $g$ and $h$ be the monotone Boolean functions computed by
these subcircuits. Let also $B_{G}\subseteq\mathbb{N}^{n}$ and
$B_{H}\subseteq\mathbb{N}^{n}$ be the sets of “exponent” vectors produced by
the subcircuits $G$ and $H$. We argue by induction on the number $s$ of gates
in $F$. In the basis case $s=1$, we have $G=x_{i}$ and $H=x_{j}$ for some
$i,j\in[n]$. Hence, $B_{G}=\\{\vec{e}_{i}\\}=A_{g}$ and
$B_{H}=\\{\vec{e}_{j}\\}=A_{h}$. So, if $F=G\lor H=x_{i}\lor x_{j}$ then
$B_{F}=B_{G}\cup B_{H}=\\{\vec{e}_{i},\vec{e}_{j}\\}=A_{f}$. If $F=G\land
H=x_{i}\land x_{j}$, then $i\neq j$ due to the multilinearity of the circuit
$F$. Hence, also in this case, we have
$B_{F}=B_{G}+B_{H}=\\{\vec{e}_{i}+\vec{e}_{j}\\}=A_{f}$.

Now suppose that the lemma holds for all monotone multilinear $(\lor,\land)$
circuits of size at most $s$, and let $F$ be a monotone multilinear
$(\lor,\land)$ circuit of size $s+1$. Since the circuit $F$ is multilinear,
both subcircuits $G$ and $H$ are also multilinear. Since each of $G$ and $H$
has at most $s$ gates, the lemma holds for both these subcircuits. Thus, both
inclusions $A_{g}\subseteq B_{G}$ and $A_{h}\subseteq B_{H}$ hold.

If $F=G\lor H$, then $B_{F}=B_{G}\cup B_{H}$ and Lemma 5 gives the inclusion
$A_{f}\subseteq A_{g}\cup A_{h}$. So, the desired inclusion $A_{f}\subseteq
B_{F}$ follows from the induction hypothesis. If $F=G\land H$, then
$B_{F}=B_{G}+B_{H}$ (Minkowski sum). Since the circuit $F$ is multilinear, the
functions $g$ and $h$ are independent, and Lemma 5 yields $A_{f}\subseteq
A_{g}+A_{h}$. So, the desired inclusion $A_{f}\subseteq B_{F}$ follows again
from the induction hypothesis.

###  7.2 Multilinear Circuits Impede Zero Terms

Lemma 6 rises a natural question: if $F=F(x,\overline{x})$ is a DeMorgan
$(\lor,\land,\neg)$ circuit computing a Boolean function $f$, when does its
monotone version ${F}^{+}=F(x,\vec{1})$ computes $f^{\triangledown}$? It can
be easily shown that such are exactly DeMorgan circuits $F$ that “impede” zero
terms in the following sense.

Every DeMorgan $(\lor,\land,\neg)$ circuit $F$ not only computes some Boolean
function $f:\\{0,1\\}^{n}\to\\{0,1\\}$ but also _produces_ (purely
syntactically) a unique set $T(F)$ of Boolean terms in a natural way:

  * $\circ$

if $F=z$ is an input literal $z\in\\{x_{i},\overline{x}_{i}\\}$, then
$T(F)=\\{z\\}$;

  * $\circ$

if $F=F_{1}\lor F_{2}$, then $T(F_{1}\lor F_{2})=T(F_{1})\cup T(F_{2})$;

  * $\circ$

if $F=F_{1}\land F_{2}$, then $T(F)=\left\\{t_{1}\land t_{2}\colon t_{1}\in
T(F_{1}),t_{2}\in T(F_{2})\right\\}$.

During the production of terms, the “annihilation” law $x\land\overline{x}=0$
is not used. So, $T(F)$ can contain _zero terms_ , that is, terms containing a
variable $x_{i}$ together with its negation $\overline{x}_{i}$. For example,
the set
$T(F)=\\{x\overline{y},x\overline{y}z,xy\overline{y},xy\overline{y}z\\}$ of
terms produced by the circuit $F=(x\lor xy)(\overline{y}\lor\overline{y}z)$
contains two zero terms $xy\overline{y}$ and $xy\overline{y}z$.

Recall that the _positive factor_ ${t}^{+}$ of a Boolean term $t$ is obtained
by replacing every its negated literal $\overline{x}_{i}$ with constant $1$.
Let us say that a DeMorgan $(\lor,\land,\neg)$ circuit $F$ computing a Boolean
function $f$ _impedes zero terms_ if positive factors ${t}^{+}$ of zero terms
$t\in T(F)$ produced by $F$ (if there are any) are implicants of
$f^{\triangledown}$, that is, if ${t}^{+}\leqslant f^{\triangledown}$ holds
for every zero term $t\in T(F)$. Note that such a circuit does _not_ forbid a
production of zero terms as such, but rather “impedes” produced zero terms to
unfold the full power of cancellations $x\land\overline{x}=0$.

######  Fact 4.

Let $F$ be a DeMorgan $(\lor,\land,\neg)$ circuit computing a Boolean function
$f$ with $f(\vec{0})=0$. The circuit ${F}^{+}$ computes $f^{\triangledown}$ if
and only if $F$ impedes zero terms.

###### Proof.

Since $F$ computes $f$, we have $f=\bigvee_{t\in T}t$, where $T=T(F)$ is the
set of all terms produced by the circuit $F$. Since $f(\vec{0})=0$, none of
the terms $t\in T$ consist of solely negated variables. For every term $t$, we
have $t^{\triangledown}=0$ (the constant $0$ function) if $t$ is a zero term,
and $t^{\triangledown}={t}^{+}$ if $t$ is a nonzero term. So, if
$T_{0}\subseteq T$ is the set of all zero terms in $T$, then (where the second
equality follows from Lemma 5(i)):

$f^{\triangledown}=\bigg{(}\bigvee_{t\in
T}t\bigg{)}^{\triangledown}=\bigvee_{t\in T}t^{\triangledown}=\bigvee_{t\in
T\setminus T_{0}}t^{\triangledown}=\bigvee_{t\in T\setminus
T_{0}}{t}^{+}\leqslant\bigvee_{t\in T}{t}^{+}={F}^{+}$

with the equality iff ${t}^{+}\leqslant f^{\triangledown}$ holds for all terms
$t\in T\setminus T^{\prime}$.

DeMorgan $(\lor,\land,\neg)$ circuits that do not produce zero terms at all
obviously impede zero terms. Such circuits were considered by several authors,
starting with Kuznetsov [22] (already in 1981, under the name “circuits
without null-chains”), where he proved a surprisingly large lower bound
$2^{n/3}$ on the size of such circuits computing an explicit $n$-variate
Boolean function. Sengupta and Venkateswaran [40] also considered DeMorgan
$(\lor,\land,\neg)$ circuits that do not produce zero terms (under the name of
“non-cancellative circuits”). They showed that for every such circuit $F$
computing a Boolean function $f$, the monotone version ${F}^{+}$ of $F$
computes $f^{\triangledown}$. Since non-cancellative circuits produce no zero
terms, this also follows from Fact 4.

Multilinear DeMorgan $(\lor,\land,\neg)$ circuits already _can_ produce zero
terms. For example, the DeMorgan $(\lor,\land,\neg)$ circuit $F=(x\lor
xy)(\overline{y}\lor\overline{y}z)$ computing $f=x\overline{y}$ is multilinear
but produces zero terms $xy\overline{y}$ and $xy\overline{y}z$. Still,
together with Lemma 6, Fact 4 implies that multilinear DeMorgan circuits
impede the produced zero terms as well.

##  8 The Read-1/Read-2 Gap Can be Exponential

Theorems 2, 1, 3 and 4 show that read-$1$ $(\lor,\land)$ circuits are not
weaker than monotone arithmetic constant-free $(+,\times)$ circuits, not
weaker than tropical $(\min,+)$ circuits, and not weaker than (non-monotone)
multilinear $(\lor,\land,\neg)$ circuits. Let us now show that already
read-$2$ $(\lor,\land)$ circuits can be much smaller than read-$1$
$(\lor,\land)$ circuits. For this, let $n=m^{2}$ and consider the following
monotone Boolean function of $n$ variables whose inputs are Boolean $m\times
m$ matrices $x=(x_{i,j})$:

$\mathrm{Lines}_{n,2}(x)=1$ iff every line of $x$ has at least one $1$,

where _lines_ are rows and columns; hence, there are $2m$ lines. Examples of
lowest ones $a\in A_{f}$ of $f=\mathrm{Lines}_{n,2}$ in the case $n=9$ is a
permutation matrix $a=\left(\begin{smallmatrix}0&1&0\\\ 1&0&0\\\
0&0&1\end{smallmatrix}\right)$ but also matrices like
$a=\left(\begin{smallmatrix}0&1&1\\\ 1&0&0\\\ 1&0&0\end{smallmatrix}\right)$.
The function $\mathrm{Lines}_{n,2}$ is a special ($2$-dimensional) version of
so-called “blocking lines” functions described in A.

The _dual_ of a Boolean function $f(x_{1},\ldots,x_{n})$ is101010As before,
for variables $x_{i}$, we write $\overline{x}_{i}$ instead of $\neg x_{i}$.
${f}^{\ast}(x_{1},\ldots,x_{n}):=\neg
f(\overline{x}_{1},\ldots,\overline{x}_{n})$. That is, we negate the input
bits as well as the obtained value. For example, by using DeMorgan rules
$\neg(x\lor y)=\neg x\land\neg y$ and $\neg(x\land y)=\neg x\lor\neg y$, we
obtain that the dual of $f(x)=\bigwedge_{S\in\mathcal{F}}\big{(}\bigvee_{i\in
S}x_{i}\big{)}$ is
${f}^{\ast}(x)=\bigvee_{S\in\mathcal{F}}\big{(}\bigwedge_{i\in
S}x_{i}\big{)}$. That is, $f(x)=1$ iff every set $S\in\mathcal{F}$ contains an
$i\in S$ with $x_{i}=1$, while ${f}^{\ast}(x)=1$ iff there is a set
$S\in\mathcal{F}$ with $x_{i}=1$ for all $i\in S$.

Recall that $\mathsf{B}^{\ast}_{k}(f)$ denotes the minimum size of a monotone
_syntactically_ read-$k$ $(\lor,\land)$ circuit computing a monotone Boolean
function $f$. In particular,
$\mathsf{B}_{k}(f)\leqslant\mathsf{B}^{\ast}_{k}(f)$ always holds.

######  Lemma 8.

For the function $f=\mathrm{Lines}_{n,2}$, we have
$\mathsf{B}_{\mathrm{lin}}(f)\geqslant\mathsf{Min}_{1}(A_{f})=\mathsf{B}_{1}(f)=2^{\Omega(\sqrt{n})}$
but
$\mathsf{Min}_{2}(A_{f})\leqslant\mathsf{B}_{2}(f)\leqslant\mathsf{B}^{\ast}_{2}(f)\leqslant
2n$ and $\mathsf{B}_{1}({f}^{\ast})\leqslant 2n$.

###### Proof.

Let $A:=A_{f}$ be the set of the lowest ones of the function
$f=\mathrm{Lines}_{n,2}$. The equality $\mathsf{Min}_{1}(A)=\mathsf{B}_{1}(f)$
and the inequality $\mathsf{Min}_{2}(A)\leqslant\mathsf{B}_{2}(f)$ are given
by Theorem 2, while the inequality
$\mathsf{B}_{\mathrm{lin}}(f)\geqslant\mathsf{B}_{1}(f)$ is given by Theorem
3.

To show the upper bound $\mathsf{B}_{1}({f}^{\ast})\leqslant 2m^{2}=2n$ for
the dual ${f}^{\ast}$ of the function $f=\mathrm{Lines}_{n,2}$, note that, for
every input matrix $x$, we have ${f}^{\ast}(x)=1$ iff $x$ has only $1$s on at
least one line of $x$. In particular, prime implicants of ${f}^{\ast}$ are the
ANDs of variables corresponding to the $2m$ lines in the matrix $x$. Hence, to
obtain a read-$1$ circuit of size $\leqslant 2m^{2}=2n$ for ${f}^{\ast}$ it is
enough to take the OR of these ANDs.

To show the lower bound $\mathsf{B}_{1}(f)=2^{\Omega(\sqrt{n})}$, recall that
$m\times m$ matrices $a\in f^{-1}(1)$ accepted by $f$ must have at least one
$1$ in each line (row or column). None of such matrices can have fewer than
$m$ $1$s, because otherwise, it would have an all-$0$ row or an all-$0$
column. So, the smallest number of $1$s in a matrix $a\in A$ is $m$, and the
matrices in $A$ with this number of $1$s are permutation matrices (with
exactly one $1$ in each row and in each column). This means that the lower
envelope $\lfloor A\rfloor$ of $A$ is the set $A_{g}$ of the lowest ones of
the perfect matching function $g=\mathrm{Match}_{m}$, and we already know that
$\mathsf{Arith}(A_{g})=2^{\Omega(m)}$ holds (Example 2). Together with Theorem
1, this yields $\mathsf{B}_{1}(f)\geqslant\mathsf{Arith}(\lfloor
A\rfloor)=\mathsf{Arith}(A_{g})=2^{\Omega(m)}$.

To show the upper bound $\mathsf{B}^{\ast}_{2}(f)\leqslant 2m^{2}=2n$, observe
that $f$ can be computed by a trivial $(\lor,\land)$ circuit

$F(x)=\bigwedge_{i=1}^{m}\big{(}\bigvee_{j=1}^{n}m_{i,j}\big{)}\land\bigwedge_{j=1}^{m}\big{(}\bigvee_{i=1}^{m}x_{i,j}\big{)}$

of size at most $2m^{2}$. That is, we first compute the $2m$ ORs of variables
along each line, and take the AND of these values. The arithmetic $(+,\times)$
version of $F$ produces the polynomial

$P(x)=\prod_{i=1}^{m}\big{(}\sum_{j=1}^{m}x_{i,j}\big{)}\cdot\prod_{j=1}^{m}\big{(}\sum_{i=1}^{m}x_{i,j}\big{)}\,.$

Since no variable $x_{i,j}$ appears in this polynomial with a degree larger
than $2$, the circuit $F$ is a syntactically read-$2$ circuit, as desired.

##  9 Concluding Remarks and Open Problems

We have shown that already very restricted monotone Boolean $(\lor,\land)$
circuits (read-$1$ circuits) capture the power of three different types of
circuits: monotone _arithmetic_ $(+,\times)$ circuits, _tropical_ $(\min,+)$
circuits, and non-monotone Boolean _multilinear_ $(\lor,\land,\neg)$ circuits.
The next natural problem is to understand the power of read-$k$ $(\lor,\land)$
circuits for $k\geqslant 2$, with $k=2$ being the first nontrivial case.

It is clear that
$\mathsf{B}_{1}(f)\geqslant\mathsf{B}_{2}(f)\geqslant\ldots\geqslant\mathsf{B}_{k}(f)\geqslant\ldots,\geqslant\mathsf{B}(f)$
holds for any monotone Boolean function $f$, where $\mathsf{B}(f)$ is the
minimum size of a monotone $(\lor,\land)$ circuit computing $f$. Super-
polynomial lower bounds on $\mathsf{B}(f)$ can be proved using the celebrated
“Method of Approximations” invented by Razborov [34, 35, 36]. However, this
method, as well as its later “symmetric” versions, can be only applied to
Boolean functions with a very special combinatorial property: _both_ minterms
and maxterms111111A _minterm_ (resp., _maxterm_) of a monotone Boolean
function $f$ is a minimal under inclusion set of variables such that setting
all these variables to $1$ (resp., to $0$) forces $f$ to output $1$ (resp.,
$0$) regardless of the values given to other variables. Since the function $f$
is monotone, every minterms intersects every maxterm. Note that prime
implicants of $f$ are ANDs of all variables in minterms; ORs of all variables
in maxterms are known as prime _implicates_ of $f$; see, for example, [7].
must be highly “dispersed” (not too many of them can share a given number of
variables in common). For example, already the application in [35] of the
Method of Approximations to prove the lower bound
$\mathsf{B}(f)=n^{\Omega(\log n)}$ for the perfect matching function
$f=\mathrm{Match}_{n}$ (which we considered in Section 5.1) is rather
nontrivial, going deeply into the structure of maxterms of this particular
function: unlike the minterms, the maxterms of $\mathrm{Match}_{n}$ are
dispersed not highly enough (see, e.g., [15, Chapter 9] for more information).

In a sharp contrast, lower bounds on the size of monotone read-$1$ circuits
can be obtained _without_ using the Method of Approximations: as demonstrated
in Section 5.1, an exponential lower bound $\mathsf{B}_{1}(f)=2^{\Omega(n)}$
for $f=\mathrm{Match}_{n}$ can be proved using a relatively simple argument:
we had only to consider the minterms of $f$. But what about read-$k$ circuits
for larger values of $k$? In particular, what about read-$2$ circuits?

######  Problem 1.

Can super-polynomial lower bounds on the size of read-$2$ or at least of
syntactically read-$2$ circuits be proved without using the Method of
Approximations?

Underlying semiring |  $\oplus$-idempotence |  $\odot$-idempotence | absorption
---|---|---|---
$(R,\oplus,\odot)$ | $x\oplus x=x$ | $x\odot x=x$ | $x\oplus(x\odot y)=x$
Arithmetic $(+,\times)$ | $-$ | $-$ | $-$
Tropical $(\min,+)$ | $+$ | $-/+$ | $+$
Read-$1$ $(\lor,\land)$ | $+$ | $-/+$ | $+$
Multilinear $(\lor,\land)$ | $+$ | $-/+$ | $+$
Tight $(\lor,\land)$ | $+$ | $+$ | $-$
Unrestricted $(\lor,\land)$ | $+$ | $+$ | $+$
Table 1: Laws allowed $(+)$ or forbidden $(-)$ in various models of circuits.
In read-$1$ and multilinear $(\lor,\land)$ circuits, as well as in tropical
$(\min,+)$ circuits the usage of “multiplicative” idempotence is only
_partially_ forbidden $(-/+)$, because the usage of the absorption law $x\lor
xy=x$ or, respectively, $\min\\{x,x+y\\}=x$ in these circuits is unrestricted;
hence, the produced “redundant” terms can be eliminated using these laws.

Monotone Boolean read-$2$ circuits constitute the _first_ model of
computation—after tropical and monotone arithmetic circuits—which can use
_both_ the idempotence $x\land x=x$ _and_ the absorption $x\lor xy=x$ laws
(albeit the usage of idempotence is restricted). Let us stress that only
_together_ these two laws can unfold their full power.

Namely, the model where absorption $x\lor xy=x$ is allowed (without any
restriction), but (when producing prime implicants) idempotence $x\land x=x$
is not allowed, is that of read-$1$ circuits considered in this paper. We have
seen that exponential lower bounds for such circuits _can_ be relatively
easily proved without using the Method of Approximations (Example 2).

On the other hand, the model where idempotence $x\land x=x$ is allowed
(without any restriction), but absorption $x\lor xy=x$ is not allowed, is that
of so-called “tight” $(\lor,\land)$ circuits. A monotone $(\lor,\land)$
circuit $F$ computing a Boolean function $f$ is _tight_ if the set
$B_{F}\subseteq\mathbb{N}^{n}$ of exponent vectors of the formal $(+,\times)$
polynomial of $F$ satisfies the equality
$\mathrm{Sup}(B_{F})=\mathrm{Sup}(A_{f})$, not only the inclusions
$\mathrm{Sup}(A_{f})\subseteq\mathrm{Sup}(B_{F})$ and
$B_{F}\subseteq(A_{f})^{\uparrow}$ as given by Lemma 1. That is, the circuit
$F$ is tight if _every_ monomial of the formal $(+,\times)$ polynomial of $F$
is a shadow of some prime implicant of $f$ (see Table 1 for a schematic
comparison of various types of circuits). Thus, tight $(\lor,\land)$ circuits
cannot use the absorption law $x\lor xy=x$, but (unlike in read-$k$ circuits)
the usage of idempotence law $x\land x=x$ is not restricted (degrees of
variables in the formal polynomial can be arbitrarily large). Note that the
read-$2$ $(\lor,\land)$ circuit used in the proof of Lemma 8 to compute the
function $\mathrm{Lines}_{n,2}$ is tight. This shows that tight circuits of
degree already $2$ can be exponentially smaller than (not necessarily tight)
read-$1$ circuits.

Still, despite their alleged power, lower bounds for tight $(\lor,\land)$
circuits (of arbitrary high degree) _can_ be proved without using the Method
of Approximations. This was demonstrated in [16, Theorem 2], where a lower
bound $2^{\Omega(n)}$ on the size of tight $(\lor,\land)$ circuits computing
the perfect matching function $\mathrm{Match}_{n}$ is shown using a fairly
simple argument similar to that we used in Section 5.1 for read-$1$ circuits.
The point is that, because of the absence of the absorption $x\lor xy=x$, the
complexity of the function $\mathrm{Match}_{n}$ is also predetermined by the
minterms of that function _alone_. However, this argument fails if the
absorption law is allowed.

In the case of read-$1$ circuits, we were able (in Theorem 1) to eliminate the
influence of absorption $x\lor xy=x$ by considering lower envelopes. But
already in read-$2$ circuits, absorption can (at least potentially) show its
power. So, a solution of Problem 1 could probably shed some light on where the
power of multiplicative idempotence $x\land x=x$ _in combination with_
absorption $x\lor xy=x$ comes from.

The next natural question is: can larger allowed “degree $k$ of idempotence”
always substantially decrease the size of read-$k$ circuits? Lemma 8 shows
that, for $k=1$, the gap $\mathsf{B}_{k}(f)/\mathsf{B}_{k+1}(f)$ can be
exponential. But what about larger values of $k$?

######  Problem 2 (Degree hierarchy).

Can the gap $\mathsf{B}_{k}(f)/\mathsf{B}_{k+1}(f)$ or at least the gap
$\mathsf{B}_{r}(f)/\mathsf{B}_{k}(f)$ be super-polynomial for $k\geqslant 2$
and $r$ not “much” smaller than $k$?

To show such a gap, we need a function $f$ for which $\mathsf{B}_{r}(f)$ is
“large” but $\mathsf{B}_{k}(f)$ is “small.” Hence, Problem 2 _cannot_ be
solved using the Method of Approximations because any lower bound on
$\mathsf{B}_{r}(f)$ obtained using this method holds for _every_ $r$.

Yet another natural question is whether the gaps between the read-$k$
$(\lor,\land)$ circuit complexities of Boolean functions $f$ and their _duals_
${f}^{\ast}$ can be large. Lemma 8 shows that, at least for $k=1$, the gap
$\mathsf{B}_{k}(f)/\mathsf{B}_{k}({f}^{\ast})$ _can_ be large.

######  Problem 3 (Duals).

Can the gap $\mathsf{B}_{k}(f)/\mathsf{B}_{k}({f}^{\ast})$ be super-polynomial
for all $k\geqslant 2$? In particular, can it be such for $k=2$?

Note that also this question _cannot_ be answered using the Method of
Approximations because $\mathsf{B}({f}^{\ast})=\mathsf{B}(f)$ always holds:
given a $(\lor,\land)$ circuit for $f$, we can obtain a $(\lor,\land)$ circuit
of the same size for the dual function ${f}^{\ast}$ by just interchanging AND
and OR gates.

As mentioned in Section 4, the model of “read-$k$ circuits” is by analogy with
the well-known computation model of “read-$k$ times branching programs.” So,
let us briefly recall this latter model. A (nondeterministic) _branching
program_ (BP), also known as a _switching-and-rectifier network_ , is a
directed acyclic graph, each edge of which is either a _switch_ (is labeled by
either a variable $x_{i}$ or by a negated variable $\overline{x}_{i}$) or is a
_rectifier_ (is labeled by constant $1$). There is one node $s$ of zero
indegree and one node $t$ of zero outdegree. The term _defined_ by an $s$-$t$
path is the AND of labels of its edges. The Boolean function _computed_ by a
branching program is the OR of terms defined by all $s$-$t$ paths. The _size_
of such a program is the total number of switches. A variable $x_{i}$ is
_read_ along a path if $x_{i}$ or $\overline{x}_{i}$ appears as a label of
some edge along that path. A branching program is a _syntactically read- $k$_
program if no variable is read more than $k$ times along _any_ $s$-$t$ path
(“syntactically” because the restriction is on _all_ $s$-$t$ paths).

$\textstyle{s}$$\textstyle{\bullet}$$\textstyle{\circ}$$\textstyle{\circ}$$\textstyle{\cdots}$$\textstyle{\circ}$$\textstyle{\circ}$$\textstyle{\circ}$$\textstyle{\circ}$$\textstyle{\circ}$$\textstyle{\cdots}$$\textstyle{\circ}$$\textstyle{\circ}$$\textstyle{\circ}$$\textstyle{\circ}$$\textstyle{\circ}$$\textstyle{\cdots}$$\textstyle{\circ}$$\textstyle{\circ}$$\textstyle{\vdots}$$\textstyle{\vdots}$$\textstyle{\vdots}$$\textstyle{\vdots}$$\textstyle{\vdots}$$\textstyle{\circ}$$\textstyle{\circ}$$\textstyle{\circ}$$\textstyle{\cdots}$$\textstyle{\circ}$$\textstyle{\bullet}$$\textstyle{t}$$\scriptstyle{{x_{1}}}$$\scriptstyle{{x_{2}}}$$\scriptstyle{{x_{r}}}$$\scriptstyle{{x_{2}}}$$\scriptstyle{{x_{3}}}$$\scriptstyle{{x_{r+1}}}$$\scriptstyle{{x_{3}}}$$\scriptstyle{{x_{4}}}$$\scriptstyle{{x_{r+2}}}$$\scriptstyle{{x_{n-r+1}}}$$\scriptstyle{{x_{n-r+2}}}$$\scriptstyle{{x_{n}}}$
Figure 1: A monotone read-$1$ branching program computing the threshold-$r$
function $\mathrm{Th}^{n}_{r}(x)=1$ iff $x_{1}+x_{2}+\cdots+x_{n}\geqslant r$.
Unlabeled edges are rectifiers (are labeled by constant $1$). This BP is even
a _syntactically_ read-$1$ BP, and has $r(n-r+1)$ switches. On the other hand,
Markov [27] has shown that _every_ monotone BP for $\mathrm{Th}^{n}_{r}$ must
have at least this number $r(n-r+1)$ of switches. Thus, at least for $k=1$,
monotone read-$k$ BPs _can_ be optimal among all monotone BPs.

In _monotone_ branching programs, none of the edges is labeled by a negated
variable $\overline{x}_{i}$. By Lemma 1, a monotone branching program $F$
computes a monotone Boolean function $f$ iff the term defined by any $s$-$t$
path is an implicant of $f$, and for every prime implicant $p$ of $f$ there is
an $s$-$t$ path in $F$ (a shadow path of $p$) along which only the variables
of $p$ are read. The program $F$ is a _semantically read- $k$_ BP if every
prime implicant of $f$ has _at least one_ shadow path along which no variable
is read more than $k$ times (see Figure 1 for an example). Thus, monotone
semantically read-$k$ branching programs correspond to read-$k$ $(\lor,\land)$
circuits considered in this paper: the restriction is only on shadow $s$-$t$
paths: there are no restrictions on the remaining $s$-$t$ paths.

For a monotone Boolean function $f$, let $\mathsf{BP}_{k}(f)$ denote the
minimum number of switches in a monotone semantically read-$k$ branching
program computing $f$. Due to the sequential nature of computation in
branching programs (rather than parallel nature, as in the case of circuits),
their structure could be easier to analyze.

######  Problem 4 (Read-$k$ branching programs).

Problems 1, 2 and 3 but for monotone semantically read-$k$ branching programs
instead of circuits, that is, for the measure $\mathsf{BP}_{k}(f)$ instead of
$\mathsf{B}_{k}(f)$.

As possible candidates for separating functions $f$ in Problems 2, 3 and 4,
one could try so-called “blocking lines” functions, including the functions
$\mathrm{Lines}_{n,k}$ and $\mathrm{Cov}_{n,k}$ described in Examples 4 and 3
of A ($n$ stands for the number of variables of these functions). Each of
these functions can be computed by a monotone syntactically read-$k$
$(\lor,\land)$ circuit with $\leqslant kn$ gates, as well as by a monotone
syntactically read-$k$ branching program with $\leqslant kn$ switches.

That the blocking lines function $\mathrm{Lines}_{n,2}$ exhibits a large
read-$1$/read-$2$ gap is shown by Lemma 8. That blocking lines functions
$\mathrm{Cov}_{n,k}$ _can_ exhibit large gaps for read-$k$ branching programs
even for larger parameters $k$ was shown by Okolnishnikova [29]. Namely, she
has proved that if $k\geqslant 4$ is a constant and $1\leqslant
r\leqslant\sqrt{k}$, then every (even not monotone but) _syntactically_
read-$r$ branching program computing $\mathrm{Cov}_{n,k}$ must have an
exponential (in $n$) number of switches. Using different (_non_ -monotone)
functions, Thathachar [44] has proved such a gap even for $r=k-1$. But, to my
best knowledge, no similar gaps are known for monotone but _semantically_
read-$k$ branching programs (where the read-$k$ restriction is only on shadow
$s$-$t$ paths).

##  Appendix A Blocking lines functions

The Boolean function $\mathrm{Lines}_{n,2}$ we used in the proof of Lemma 8 is
just a very special case of the following more general construction of Boolean
functions that have small read-$k$ circuits but could (apparently) require
large read-$r$ circuits for $r<k$. That these functions sometimes indeed _can_
exhibit such gaps is shown by Lemma 8, as well as by the aforementioned result
of Okolnishnikova [29].

Let ${\cal L}\subseteq 2^{P}$ be a family of subsets of a finite set $P$; let
us call elements $p\in P$ _points_ , and sets $L\in{\cal L}$ _lines_. Suppose
that the family ${\cal L}$ is $m$-_uniform_ (each line has exactly $m$
points), and is $k$-_regular_ (each point belongs to exactly $k$ lines). By
double-counting, we have $m|{\cal L}|=k|P|$. The _blocking lines function_
$f_{{\cal L}}$ has $n=|P|$ variables $x_{p}$, one for each point $p\in P$ and,
for every input $x\in\\{0,1\\}^{P}$, $f_{{\cal L}}(x)=1$ iff the set of points
$S_{x}=\\{p\in P\colon x_{p}=1\\}$ blocks (intersects) every line $L\in{\cal
L}$. The monotone circuit $F_{{\cal L}}(x)=\bigwedge_{L\in{\cal
L}}\big{(}\bigvee_{p\in L}x_{p}\big{)}$ computes $f_{{\cal L}}$ and has
$(m-1)|{\cal L}|+(|{\cal L}|-1)=m|{\cal L}|-1$ fanin-$2$ gates. Moreover,
since no point belongs to more than $k$ lines, $F_{{\cal L}}$ is a read-$k$
circuit. In particular, we have an upper bound $\mathsf{B}_{k}(f_{{\cal
L}})\leqslant m|{\cal L}|=k|P|=kn$. Note that for the dual ${f}^{\ast}_{{\cal
L}}(x)=\bigvee_{L\in{\cal L}}\bigwedge_{p\in L}x_{p}$ of $f_{{\cal L}}$, we
even have $\mathsf{B}_{1}({f}^{\ast}_{{\cal L}})\leqslant kn$, that is, the
duals of blocking lines functions can be computed by small _read- $1$_
circuits. Since none of the points belongs to more than $k$ lines, every
implicant $t_{S}=\bigwedge_{p\in S}x_{p}$ of $f_{{\cal L}}$ corresponds to a
blocking set $S\subseteq P$ consisting of $|S|\geqslant|{\cal L}|/k$ points,
while shortest (prime) implicants $t_{S}$ of $f_{{\cal L}}$ (those with the
smallest number of variables) correspond to _smallest_ blocking sets, that is,
blocking sets $S\subseteq P$ consisting of $|S|=|{\cal L}|/k$ pairwise
noncollinear points; two points are _collinear_ if they both belong to some
line. Note that maxterms of $f_{{\cal L}}$ are sets $\\{x_{p}\colon p\in L\\}$
of variables corresponding to lines $L\in{\cal L}$, while minterms of
$f_{{\cal L}}$ are sets $\\{x_{p}\colon p\in S\\}$ of variables corresponding
to blocking sets $S\subseteq P$, none proper subset of which is a blocking
set.

Each point of a smallest blocking set $S\subseteq P$ blocks (intersects) its
_own_ collection of $k$ lines: for every point $p\in S$ there is a collection
${\cal L}_{p}\subseteq{\cal L}$ of $|{\cal L}_{p}|=k$ lines such that ${\cal
L}_{p}\cap{\cal L}_{q}=\emptyset$ holds for all points $p\neq q\in S$ (for,
otherwise, points $p$ and $q$ would be collinear). That is, each point $p\in
S$ is the _only_ point of $S$ blocking the $k$ lines ${\cal L}_{p}$. In other
words, each variable $x_{p}$ of a shortest prime implicant
$t_{S}=\bigwedge_{p\in S}x_{p}$ of $f_{{\cal L}}$ blocks its _own_ collection