Two notes on Thm. 9.17 (lower-bounds criterion for monotone circuits)

NOTE 1: Although I have not stated this explicitly, Thm. 917 holds also for monotone circuits with unbounded fanin AND and OR gates. This follows from its proof: the fanin has no influence when forming the approximators of gates. At an AND gate, the left approximator is just the AND of the left approximators of its inputs. The right approximator is then formed using the Switching Lemma (Lemma 9.15), which does not depend on the number of clauses, only on their length. At OR gates, the situation is dual.

NOTE 2: One small "subtlety" was not made explicit in the given proof of this theorem. It concerns the "border cases" when one of $\CC{f}$ or $\DD{f}$ becomes empty (has no clauses or no monomials at all). In these cases, the Monotone Switching Lemma (Lemma 9.15) does not hold, and it remained not clear how to assign approximators of gates in such cases. This may happen, say, when we are at an AND gate $f=g\land h$, and $\CC{f}$ consists of $r$ or more disjoint clauses. The application of the the Monotone Switching Lemma (Lemma 9.15) to $\CC{f}$ gives then an empty DNF $\DD{f}$. As customary, we interpret an empty CNF as the constant $1$ function, and an empty DNF as the constant $0$ function.

So, let us now make this "subtlety" explicit. Recall that we assigned approximators $(\CC{f},\DD{f})$ inductively as follows; here $\left(\CC{f} \right)^*$ stays for the DNF obtained by applying the Switching Lemma to the CNF $\CC{f}$, and dually for $\left(\DD{f} \right)^*$: \begin{align} f&=g\land h \ \ \Longrightarrow\ \ \CC{f}:=\CC{g}\land\CC{h}\ \mbox{ and }\ \DD{f}:=\left(\CC{f} \right)^*\\ f&=g\lor h \ \ \Longrightarrow\ \ \DD{f}:=\DD{g}\lor\DD{h}\ \mbox{ and }\ \CC{f}:=\left(\DD{f} \right)^* \end{align} In the case when one of $\CC{f}$ or $\DD{f}$ is empty, we do the following: \begin{align} f&=g\land h \ \mbox{ and }\ \CC{f}\equiv 1\ \ \Longrightarrow\ \ \DD{f}:=\DD{g}\\ f&=g\lor h \ \mbox{ and }\ \DD{f}\equiv 0\ \ \Longrightarrow\ \ \CC{f}:=\CC{g} \end{align} Note that the "cross intersection" property $\DD{f}\leq\CC{f}$ is then trivially fulfilled.

Recall that an approximator $(\CC{f},\DD{f})$ of $f$ introduces a new error on input $x\in\{0,1\}^n$ if the approximators of $g$ and of $h$ did not make an error on $x$, but the approximator of $f$ does. That is, $\CC{g}(x)=\DD{g}(x)=g(x)$ and $\CC{h}(x)=\DD{h}(x)=h(x)$, but either $\CC{f}(x)\neq f(x)$ or $\DD{f}(x)\neq f(x)$ holds.

Suppose now that one of $\CC{f}$ or $\DD{f}$ is empty, say, $\CC{f}\equiv 1$. We claim that then no new error is introduced at $f=g\land h$. To see this, let $x\in\{0,1\}^n$ be an input on which a new error is introduced. Since there was no error on $x$ at input gates $g$ and $h$, we have that $\CC{g}(x)=\DD{g}(x)=g(x)$ and $\CC{h}(x)=\DD{h}(x)=h(x)$. Hence, $\CC{f}(x):=\CC{g}(x)\land \CC{h}(x)=g(x)\land h(x)=f(x)$, meaning that the left approximator $\CC{f}$ introduces no error on $x$. So, the error must be introduced at the right approximator $\DD{f}:=\DD{g}$, i.e. $f(x)=1$ and $\DD{f}(x)=0$. But $f(x)=g(x)\land h(x)=1$ implies that $g(x)=1$, and hence also $\DD{g}(x)=1$, since $x$ was not an error at gate $g$. Hence, $\DD{f}(x)=\DD{g}(x)=1=f(x)$, and we have no error at $f$.

The case of an Or gate $f=g\lor h$ is dual.

S. Jukna, June 2014

Back to the home page of the book.