Boolean Circuit Complexity Fall Semester, 1994-5

Lecture 8: December 15

Lecturer: Uri Zwick Scribe: Barak Adorian

8.1 Exponential lower bound for monotone circuit size

8.1.1 Reminder

General motivation

In the previous lesson we have stated the following theorem:

Theorem 8.1 (Alon,Boppana 1987)

C_{M_{2}}(CLIQUE_{k}(n)) = e^{Ω(\sqrt{k})}, for k = O ((\frac{n}{log n})^{2/3}).

The theorem, as stated, implies a lower bound of e^{Ω(n^{1/6−o(1)})} on the complexity of a Boolean function with n variables, as the clique function has (_{2}^{n}) variables. In this lesson we present a proof for a slightly weaker version of the theorem, i.e., the same lower bound C_{M_{2}}(CLIQUE_{k}(n)) = e^{Ω(\sqrt{k})} but only for k = O ((\frac{n}{log^{2} n})^{1/3}). We will, therefore, obtain a lower bound of :

e^{Ω(( \frac{n}{log^{2} n})^{1/6})}.

The proof requires definitions of a number of symbols and notions:

• ⌈X⌉ - a clique indicator on a vertex set X, where |X| ≤ l.

• approximator - an expression C of the form C = ⋁_{i=1}^{m′}⌈X_{i}⌉ where m′ ≤ m. The constants 0 and 1 may also serve as approximators. ^{1}

• sunflower - a collection of sets Z_{1}, …, Z_{p} such that ∃Z′ for which 1 ≤ i < j ≤ p ⇒ Z_{i} ∩ Z_{j} = Z′. Replacing the sets of a sunflower with its center (Z′) is known as plucking.

• approximate OR - of two approximators ⋁_{i=1}^{m_{1}}⌈X_{i}⌉, ⋁_{j=1}^{m_{2}}⌈Y_{j}⌉ written ⋁_{i=1}^{m_{1}}⌈X_{i}⌉ ⊔ ⋁_{j=1}^{m_{2}}⌈Y_{j}⌉ is defined to be ⋁_{i=1}^{m′}⌈Z_{i}⌉ where the collection of vertices sets Z_{1}, …, Z_{m′} (m′ ≤ m) is generated from the vertex sets X_{1}, …, X_{m_{1}}, Y_{1}, …, Y_{m_{2}} by repeatedly finding and plucking sunflowers.

1m and l are constants that depend on k and n.

• approximate AND - of two approximators ⋁_{i=1}^{m_{1}}⌈X_{i}⌉, ⋁_{j=1}^{m_{2}}⌈Y_{j}⌉ written ⋁_{i=1}^{m_{1}}⌈X_{i}⌉ ⊓ ⋁_{j=1}^{m_{2}}⌈Y_{j}⌉ is defined to be the product of the following operation: from the OR expression of ⋁_{i,j}⌈X_{i} ∪ Y_{j}⌉ remove all ⌈X_{i} ∪ Y_{j}⌉ for which |X_{i} ∪ Y_{j}| > l, reduce the number of remaining clique indicators, by plucking sunflowers, to at most m.

A sketch of the proof

Using the above we have shown how to obtain an approximator for any monotone circuit, by replacing OR and AND gates with approximate OR and AND, respectively. Our goal is to show that any approximator is liable to fail for a large number of test graphs, while each gate replacement could have been responsible only for a small number of these errors. Thus we can conclude that the number of gates in the monotone circuit, to begin with, was large.

8.1.2 The case of CLIQUE_{3}(n)

We have started with the case of k = 3, choosing l to be 2, (which implies that each clique indicator is simply an edge indicator), and proved the following claims:

Claim 8.2 Each approximator, is either identically 0 or outputs 1 on at least half of the negative test graphs.

Claim 8.3

• C_{1} ∨ C_{2} ≤ C_{1} ⊔ C_{2} always holds.

• C_{1} ∧ C_{2} ≤ C_{1} ⊓ C_{2} fails for at most m^{2} positive test graphs.

Conclusion 8.4 If β is a monotone circuit for the function CLIQUE_{3}(n) and the approximator for β is identically 0, then β contains at least \frac{(_{3}^{n})}{m^{2}} AND gates.

The last follows from Claim 8.3 since such an approximator fails for all (_{3}^{n}) positive test graphs. Only approximate AND gates can cause such errors, and each such gate can fail for at most m^{2} graphs.

We now conclude the proof for the k = 3 case by proving the following claim:

Claim 8.5

• C_{1} ⊓ C_{2} ≤ C_{1} ∧ C_{2} always holds.

• C_{1} ⊔ C_{2} ≤ C_{1} ∨ C_{2} fails for at most 2^{n−p} negative test graphs. ^{2}

Proof: Assume that C_{1} = ⋁_{X∈A}⌈X⌉ and C_{2} = ⋁_{Y ∈B}⌈X⌉. From the choice l = 2, it follows that X ∈ A, Y ∈ B, X ≠ Y ⇒ |X ∪ Y | > l, and therefore ⌈X ∪ Y ⌉will not appear in the approximate AND. Thus we are left with ⋁_{X∈A}⌈X⌉ ⊓ ⋁_{Y ∈B}⌈Y ⌉ = ⋁_{X∈A∩B}⌈X⌉, and the necessity for plucking never arises. The first inequality follows immediately from the stated equation.

In order to prove the second statement we count the negative test graphs for which C_{1} ⊔ C_{2} > C_{1} ∨ C_{2}. Recall that in the case of approximate OR only plucking could cause any difference between the circuit and its approximator. The choice l = 2, causes every sunflower to be either a matching or a star graph, plucking these sunflowers results in the empty set in the first case, or a single node in the second. The clique indicators of both cases are the constant 1.

Thus if A ∪ B contains a sunflower S of size p, we should count the negative test graphs for which ⋁_{X∈A∪B}⌈X⌉ = 0. In particular the equation ⋁_{X∈S}⌈X⌉ = 0 holds for such graphs.

Given a sunflower S of size p, the probability that a negative test graph would satisfy ⋁_{X∈S}⌈X⌉ = 0 is exactly 2^{−p}. Multiplying this by the number of negative graphs yields 2^{n−p} as required.

Conclusion 8.6 If β is a monotone circuit for the function CLIQUE_{3}(n) and the approximator for β is not identically 0, then β contains at least 2^{p−1} OR gates.

From Claim 8.2 we conclude that the approximator will fail for at least 2^{n−1} negative graphs, but by Claim 8.5 only approximate OR gates can cause the errors and each such gate can fail for at most 2^{n−p} graphs.

Obtaining the lower bound

We can now choose values for p to obtain explicit lower bounds, using Conclusions 8.4 and 8.6 . Choosing p = 6 log n we conclude that any monotone circuit for CLIQUE_{3}(n) contains either Ω(\frac{n^{3}}{log^{4} n}) AND gates, or Ω(n^{6}) OR gates, and therefore contains at least Ω(\frac{n^{3}}{log^{4} n}) gates.

The following lemma enables us to bound the number of AND gates in any monotone circuit for CLIQUE_{3}(n).

Lemma 8.7 If a monotone function f on n variables is computed by a monotone circuit containing k AND gates, then it can also be computed by a monotone circuit containing k AND gates and O(k(n + k)) OR gates.

2p is the number of sets in a sunflower. The parameters m, l and p are chosen satisfy the relation m = (p − 1)^{l}l!.

Proof: Let x_{1}, …, x_{n} be the arguments of f, and y_{1}, …, y_{k} be the functions calculated by the k AND gates, in the monotone circuit for the function f. Let z_{i}^{1}, z_{i}^{2} be the inputs of the gate that computes y_{i}. Clearly z_{i}^{1}, z_{i}^{2} are ORs of a subset of the set x_{1}, …, x_{n}, y_{1}, …, y_{k}, each such OR may be calculated by O(n+k) OR gates. Similarly, the output of the circuit is an OR of a subset of x_{1}, …, x_{n}, y_{1}, …, y_{k}, and therefore may also be calculated by O(n + k) ORs. The total number of OR gates required is therefore O(k(n + k)).

Remark: The bound on the number of OR gates may be improved to O(\frac{k(k+n)}{log k}).

Conclusion 8.8 Any monotone circuit for CLIQUE_{3}(n) contains Ω (\frac{n^{3}}{log^{4} n})AND gates.

The conclusion follows immediately from the fact that if such circuit does not contain Ω (\frac{n^{3}}{log^{4} n}) AND gates, it contains O(n^{6}) OR gates, and therefore, by Lemma 8.7 it contains Ω(n^{3}) AND gates. Using a tighter analysis performed by Alon and Boppana, the bound on the number of AND gates can be improved to Ω (\frac{n^{3}}{log^{3} n}) .

8.1.3 The general case (k ≥ 3)

The proof of Theorem 8.1 (in its “weaker form”) follows the ideas of the special case k = 3, introducing three claims, resembling Claims 8.2, 8.3, 8.5 .

Claim 8.9 Each approximator, is either identically 0 or outputs 1 on at least

(1 − \frac{(_{2}^{l})}{k − 1}) (k − 1)^{n}

of the negative test graphs.

Proof: Let C = ⋁_{i=1}^{m′}⌈X_{i}⌉ be an approximator which is not identically 0. Clearly m′ ≥ 1 and C ≥ ⌈X_{1}⌉. There is no clique on X_{1} iff two of the vertices in X_{1} are colored by the same color. Let l′ = |X_{1}|. Given a negative test graph, the probability that two of X_{1}’s vertices are identically colored is bounded from above by (_{2}^{l′})/(k − 1) ≤ (_{2}^{l})/(k − 1). The probability of a clique on X_{1} is, therefore, at least

1 − \frac{(_{2}^{l})}{k − 1}.

Multiplying this by the number of negative test graphs, gives a lower bound on the number of such graphs, for which C outputs 1, and concludes the proof.

Choose now l = ⌊\sqrt{k}⌋. It follows that each approximator that is not identically 0, outputs 1 on at least half of the negative test graphs.

Claim 8.10

• C_{1} ∨ C_{2} ≤ C_{1} ⊔ C_{2} always holds.

• C_{1} ∧ C_{2} ≤ C_{1} ⊓ C_{2} fails for at most m^{2}(_{k−l−1}^{n−l−1}) positive test graphs.

Proof: The first claim is trivial since inequality may arise only in case of plucking, and in such case a clique on one of the sets of the sunflower implies a clique on the center.

In order to prove the second claim, we count the positive graphs for which C_{1} ∧ C_{2} > C_{1} ⊓ C_{2}. The process of obtaining C_{1} ⊓ C_{2} from C_{1} ∧ C_{2} involves three steps: first, replacing ⌈X_{i}⌉ ∧ ⌈Y_{j}⌉ with ⌈X_{i} ∪ Y_{j}⌉. Though the two functions are not the same, they agree for all positive graphs.^{3} The second step requires the deletion of all the ⌈X_{i} ∪ Y_{j}⌉ terms for which |X_{i} ∪ Y_{j}| ≥ l + 1. Each such X_{i} ∪ Y_{j} may be a subset of at most (_{k−l−1}^{n−l−1}) sets of vertices of size k, and each such set defines a single positive test graph. Therefore, for each ⌈X_{i} ∪ Y_{j}⌉ we delete, at most (_{k−l−1}^{n−l−1}) positive graphs are lost. This second step may be required for at most m^{2} different X_{i} ∪ Y_{j} sets. At last we may pluck some sunflowers, this can only increase the value of the function, and therefore can not enlarge the class of graphs satisfying C_{1} ∧ C_{2} > C_{1} ⊓ C_{2}.

From the sum of the three steps, we conclude that at most m^{2}(_{k−l−1}^{n−l−1}) positive test graphs satisfy C_{1} ∧ C_{2} > C_{1} ⊓ C_{2}.

Conclusion 8.11 If β is a monotone circuit for the function CLIQUE_{k}(n) and the approximator for β is identically 0, then β contains at least

\frac{(_{k}^{n})}{m^{2}(_{k−l−1}^{n−l−1})}

AND gates.

The conclusion follows from Claim 8.10 since a 0 approximator fails for all (_{k}^{n}) positive test graphs, while only approximate AND gates can cause errors, and each such gate fails for at most m^{2}(_{k−l−1}^{n−l−1}) positive graphs.

Claim 8.12 Each of the following inequalities

• C_{1} ⊔ C_{2} ≤ C_{1} ∨ C_{2}

• C_{1} ⊓ C_{2} ≤ C_{1} ∧ C_{2} fails for at most

3Recall that a positive graph is a clique, therefore if there exists a clique on two sets, there is a clique on their union.

m^{2} [\frac{(_{2}^{l})}{(k − 1)}]^{p} (k − 1)^{n}

negative test graphs.

Proof: From the proof of Claim 8.10 it follows that sunflower plucking must take place in order for any of these inequalities to fail. Since the first fail iff C_{1} ⊔ C_{2} ≠ C_{1} ∨ C_{2}, which may be true only if plucking was used in the computation of C_{1} ⊔ C_{2}. Examining the three steps involved in the computation of C_{1} ⊓ C_{2} from C_{1} ∧ C_{2}, we may conclude that the second inequality can fail only because of the third step, in which sunflowers are being plucked.

We will now show that for a sunflower Z_{1}, …, Z_{p} with center Z, the probability of ⌈Z⌉ = 1 while ⋁_{i=1}^{p}⌈Z_{i}⌉ = 0 for a random negative test graph is at most [(_{2}^{l})/(k − 1)]^{p}. To do so we introduce the term properly colored: a set of vertices is properly colored if each vertex in the set is colored with a different color. Note that the probability we are after is the probability that Z is properly colored (P C) while Z_{1}, …, Z_{p} are not.

P r[Z is P C but Z_{1}, …, Z_{p} are not P C]
≤ P r[Z_{1}, …, Z_{p} are not P C | Z is P C]
=  ∏_{i=1}^{p} P r[Z_{i} is not P C | Z is P C]
≤  ∏_{i=1}^{p} P r[Z_{i} is not P C]

The first inequality holds by the definition of conditional probability. The following equality holds by the mutual independence of the events {Z_{i} is not PC | Z is PC }, and the last holds because “Z is PC” is negatively correlated with other events.

As we have shown in the proof for Claim 8.9, P r[Z_{i} is not P C] ≤ (_{2}^{l})/(k − 1), and thus the probability of a random negative test graph satisfying ⌈Z⌉ = 1 and ⋁_{i=1}^{p}⌈Z_{i}⌉ = 0 is at most [(_{2}^{l})/(k − 1)]^{p}. Multiplying this by the maximal number of plucking required (m^{2}), and the number of negative graphs, we obtain the required bound.

Conclusion 8.13 If β is a monotone circuit for the function CLIQUE_{k}(n) and the approximator for β is not identically 0, then β contains at least

\frac{1}{2m^{2}} [\frac{(k − 1)}{(_{2}^{l})}]^{p}

gates.

From Claim 8.9 together with the choice l = ⌊\sqrt{k}⌋ we conclude that the approximator fails for at least (k − 1)^{n}/2 of the negative test graphs, but by Claim 8.12 each gate could be responsible for at most m^{2}[(_{2}^{l})/(k − 1)]^{p}(k − 1)^{n} of these errors.

Remark: By our choice of l it follows that (k − 1)/(_{2}^{l}) ≥ 2, so we may replace

\frac{1}{2m^{2}} [\frac{(k − 1)}{(_{2}^{l})}]^{p} with \frac{1}{m^{2}} 2^{p−1}

in Conclusion 8.13 .

Obtaining the lower bound

We have, by now, established a lower bound of

\frac{1}{m^{2}} · min \{\frac{(_{k}^{n})}{(_{k−l−1}^{n−l−1})} , 2^{p−1}\}

on the number of gates, where l = ⌊\sqrt{k}⌋. We should still show how to choose p to obtain the desired bound. Since

\frac{(_{k}^{n})}{(_{k−l−1}^{n−l−1})} = \frac{n! (n − k − 1)! (n − k)!}{k! (n − k)! (n − l − 1)!} = \frac{n(n − 1) … (n − l)}{k(k − 1) … (k − l)} > (\frac{n}{k})^{l+1} ,

the choice p = ⌈\sqrt{k} log_{2} n⌉ + 1 , yields both 2^{p−1} ≥ n^{\sqrt{k}} and

m = (p − 1)^{l}l! ≤ (⌈\sqrt{k} log_{2} n⌉)^{\sqrt{k}}(\sqrt{k})^{\sqrt{k}} ≤ (2k log_{2} n)^{\sqrt{k}}.  (8.1)

Thus, we get

\frac{1}{m^{2}} \frac{(_{k}^{n})}{(_{k−l−1}^{n−l−1})} > (\frac{1}{2k log n})^{2\sqrt{k}} (\frac{n}{k})^{\sqrt{k}} = (\frac{n}{4k^{3} log^{2} n})^{\sqrt{k}} .  (8.2)

Let us assume that n/4k^{3} log^{2} n ≥ 2, or equivalently, that k ≤ (n/8 log^{2} n)^{1/3}. It follows from inequality 8.2 that

\frac{1}{m^{2}} \frac{(_{k}^{n})}{(_{k−l−1}^{n−l−1})} > 2^{\sqrt{k}}

and from inequality 8.1 that

\frac{1}{m^{2}} 2^{p−1} ≥ n^{\sqrt{k}} (\frac{1}{2k log n})^{2\sqrt{k}} = (\frac{n}{4k^{2} log^{2} n})^{\sqrt{k}} ≥ 2^{\sqrt{k}}.

This implies that the number of gates is at least 2^{\sqrt{k}}.

8 Lecture 8: December 15 Conclusion We have shown that for

k ≤ (\frac{n}{8 log^{2} n})^{1/3}

C_{M}(CLIQUE_{k}(n)) ≥ 2^{\sqrt{k}} holds. In particular, for

k = (\frac{n}{8 log^{2} n})^{1/3}

we have established a lower bound of 2^{Ω((\frac{n}{log^{2} n})^{1/6})}.