Approximation Lemma: If a monotone boolean function $f$ can be computed by a monotone boolean circuit of size $t$, then $f$ can be approximated by a cross-intersecting pair $(C,D)$, where $C$ has at most $t\cdot (\length{1}-1)^{\factor{1}\cdot \length{0}}$ long clauses, and $D$ has at most $ t\cdot (\length{0}-1)^{\factor{0}\cdot \length{1}}$ long monomials.Remark: Note that the requirement that the pair $(C,D)$ must be cross-intersecting is crucial: the CNF/DNF pair $C=x_1\land x_2\land\cdots\land x_n$ and $D=x_1\lor x_2\lor\cdots \lor x_n$ approximates any nonconstant monotone boolean function $f(x_1,\ldots,x_n)$.
Remark: In the case of circuits with monotone real-valued gates, the same criterion holds with $t\cdot (\length{1}-1)^{\factor{1}\cdot \length{0}}$ and $ t\cdot (\length{0}-1)^{\factor{0}\cdot \length{1}}$ replaced by $t\cdot (2\length{1})^{\factor{1}\cdot \length{0}+1}$ and $ t\cdot (2\length{0})^{\factor{0}\cdot \length{1}+1}$; this follows from the proof of Theorem 9.21 (reducing the real case to the boolean case).
Proof: Let $X_0\subseteq \{0,1\}^n$ be the set of all negative inputs, and $X_1\subseteq \{0,1\}^n$ the set of all positive inputs of the function computed by our circuit. A rough idea of the proof is simple: we use switching lemmas to inductively associate with the gates their ``approximators,'' and to show that ar each gate, all errors introduced by its approximator can be corrected y adding a long CNF with not too many clauses or a long DNF with not too many monomials. Then the approximator of the output gate (where our function is computed) als can be corrected in this way. This will give us the desired CNF/DNF pair $(C,D)$.
Let $f=g\ast h$ be a gate in our circuit. That is, $f$ is a function computed at some node of the circuit, and $g$ and $h$ are functions computed at its inputs. By an \emph{approximator} of this gate we will mean a pair $(\CC{f},\DD{f})$, where $\CC{f}$ is a CNF consisting of only short clauses (a \emph{left} approximator of $f$) and $\DD{f}$ is a DNF consisting of only short monomials (a \emph{right} approximator of $f$) such that $\DD{f}(x)\leq \CC{f}(x)$ holds for all input vectors $x$.
Under an error introduced by an approximator $(\CC{f},\DD{f})$ of a gate $f$ we will understand an input $x\in X_0\cup X_1$ on which 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)$.
We define approximators inductively as follows.
Case 1: $f$ is an input variable, say, $f=x_i$. In this case we take $\CC{f}=\DD{f}:= x_i$. It is clear that this approximator introduces no errors.
Case 2: $f$ is an And gate, $f=g\land h$. In this case we take $\CC{f}:=\CC{g}\land \CC{h}$ as the left approximator of $f$; hence, $\CC{f}$ introduces no errors. To define the right approximator of $f$ we use the CNF-to-DNF Switching Lemma to convert the short CNF $\CC{f}$ into a short DNF $\DD{f}$; hence, $\DD{f}\leq \CC{f}$. If the CNF $\CC{f}$ is empty (that is, $\CC{f}=1$), then we let $\DD{f}:=\DD{g}$. Let $E_f$ be the set of inputs on which $\DD{f}$ introduces an error, that is, \[ E_f=\left\{x\in X_1\colon \CC{f}(x)=f(x)=1\ \mbox{ but }\ \DD{f}(x)=0\right\}. \] By the CNF-to-DNF Switching Lemma, all these errors can be ``corrected'' by adding to $\DD{f}$ a relatively small number of long monomials: there is a DNF $D$ consisting of at most $(\length{0}-1)^{\factor{0}\cdot \length{1}}$ long monomials such that $D(x)=1$ holds for all $x\in E_f$. If the CNF $\CC{f}$ was empty, then $E_f=\emptyset$. To see this, let $x$ be an input on which an error is introduced. Since the left (empty) approximator $\CC{f}$ cannot produce any error, this 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$.
Case 3: $f$ is an And gate, $f=g\lor h$. In this case we take $\DD{f}:=\DD{g}\lor \DD{h}$ as the right approximator of $f$; hence, $\DD{f}$ introduces no errors. To define the left approximator of $f$ we use the DNF-to-CNF Switching Lemma to convert the short DNF $\DD{f}$ into a short CNF $\CC{f}$; hence, $\DD{f}\leq \CC{f}$. If the DNF $\DD{f}$ is empty (that is, $\DD{f}=0$), then we let $\CC{f}:=\CC{g}$. Let $E_f$ be the set of inputs on which $\CC{f}$ introduces an error, that is, \[ E_f=\left\{x\in X_0\colon \CC{f}(x)=f(x)=0\ \mbox{ but }\ \CC{f}(x)=1\right\}. \] By the DNF-to-CNF Switching Lemma, all these errors can be ``corrected'' by adding to $\CC{f}$ a relatively small number of long clauses: there is a CNF $C$ consisting of at most $(\length{1}-1)^{\factor{1}\cdot \length{0}}$ long clauses such that $C(x)=0$ holds for all $x\in E_f$.
If the DNF $\DD{f}$ was empty, then $E_f=\emptyset$. To see this, let $x$ be an input on which an error is introduced. Since the right (empty) approximator $\DD{f}$ cannot produce any error, this error must be introduced at the left approximator $\CC{f}:=\CC{g}$, i.e. $f(x)=0$ and $\CC{f}(x)=1$. But $f(x)=g(x)\lor h(x)=0$ implies that $g(x)=0$, and hence also $\CC{g}(x)=0$, since $x$ was not an error at gate $g$. Hence, $\CC{f}(x)=\CC{g}(x)=0=f(x)$, and we have no error at $f$.
Proceeding in this way we will reach the last gate of our circuit computing the given function $F$. Let $(\CC{F},\DD{F})$ be its approximator, and let $E$ be the set of all inputs $x\in X_0\cup X_1$ on which $F$ differs from at least one of the functions $\CC{F}$ or $\DD{F}$. Since at input gates (= variables) no error was made, for every such input $x\in E$, the corresponding error must be introduced at some intermediate gate. That is, for every $x\in E$ there is a gate $f$ such that $x\in E_f$ (approximator of $f$ introduces an error on $x$ for the first time). But we have shown that, for each gate, all these errors can be corrected by adding a DNF consisting of at most $(\length{0}-1)^{\factor{0}\cdot \length{1}}$ long monomials or a CNF consisting of at most $(\length{1}-1)^{\factor{1}\cdot \length{0}}$ long clauses.
Since we have only $t$ gates, all such errors $x\in E$ can be corrected by adding a DNF $D$ consisting of at most $t\cdot (\length{0}-1)^{\factor{0}\cdot \length{1}}$ long monomials and a CNF $C$ consisting of at most $t\cdot (\length{1}-1)^{\factor{1}\cdot \length{0}}$ long clauses. So, if we take $C':=\CC{F}\land C$ and $D':=\DD{F}\lor D$, then the pair $(C',D')$ is cross-intersecting (because every monomial of $\DD{F}$ intersects every clause of $\CC{F}$), and approximates the function $F$ computed by the entire circuit. $\Box$
Theorem (Lower bounds criterion): Let $f$ be a monotone boolean function. If $f$ can be computed by a monotone boolean circuit of size $t$, then there exists a family $\A$ of $|\A|\leq t\cdot (\length{0}-1)^{\factor{1}\cdot \length{1}}$ sets of $\mes_1$-length $\geq \length{1}$, a family $\B$ of $|\B|\leq t\cdot (\length{1}-1)^{\factor{0}\cdot \length{0}}$ sets of $\mes_0$-length $\geq \length{0}$, and a set $I$ of size $|I|\leq (\length{0}-1)^{\factor{0}}$ such thatProof: By the Approximation lemma, the function $f$ can then be approximated by a cross-intersecting CNF/DNF pair $(C,D)$, where $C$ has at most $t\cdot r^{\factor{1}\cdot s}$ long clauses, and $D$ has at most $ t\cdot s^{\factor{0}\cdot r}$ long monomials. Let $\f_1$ be the family of all positive inputs, and $\f_0$ the family of all negative inputs of $f$. There are two possible cases: either the CNF $C$ contains at least one short clause, or not.
- either every positive input of $f$ avoiding $I$ contains some set of $\A$,
- or every negative input of $f$ avoids some set of $\B$.
Case 1: $C$ contains a short clause, that is, a clause $q$ of $\mes_0$ length $\mes_0(q)\leq s-1$; hence, $q$ has $|q|\leq \mes_0(q)^{\factor{0}}\leq (s-1)^{\factor{0}}$ variables. Since the pair $(C,D)$ approximates our function, we know that the DNF $D$ must accept all sets of $\f_1$ ($k$-cliques). This means that every $S\in\f_1$ must contain some monomial of $D$. Remove now from $D$ all short monomials, and let $D'$ be the resulting long DNF. After that, some of sets in $\f_1$ may contain none of the monomials of $D'$. But since the pair $(C,D)$ is cross-intersecting, the clause $c$ must intersect all monomials of $D$ and, in particular, all short monomials of $D$. So, every set $S\in\f_1$ must either contain a monomial of $D'$, or must contain at least one of the $|q|\leq (s-1)^{\factor{0}}$ variables of~$c$. So, in this case the first alternative (1) of the theorem holds with $\A:=D'$ and $I:=q$.
Case 2: $C$ contains no short clauses. Since the pair $(C,D)$ approximates our function, we know that the CNF $C$ must reject all sets $\f_0$. That is, for every set of $\f_0$ there must be a clause $q$ in $C$ such that $S\cap q=\emptyset$. So, in this case the second alternative (2) of the theorem immediately holds with $\B:=C$ $\Box$
Back to the comment.