Boolean Circuit Complexity Fall Semester, 1994-5

Lecture 2: November 3

Lecturer: Uri Zwick Scribe: Izik Pe’er

2.1 Lupanov’s Theorem

2.1.1 Reminder

In the previous lesson we have proved the following theorem:

Theorem 2.1 (Shannon) Almost every Boolean function of n bits requires a B_{2}-circuit of size at least \frac{2^{n}}{n} for their implementation.

We will try get an upper bound on the Boolean complexity of arbitrary Boolean functions, and we will see that the \frac{2^{n}}{n} bound is tight (up to a negligible additive factor).

We have already seen the following trivial upper bound:

Theorem 2.2 For every function f ∈ B_{n}: C_{B_{2}}(f) ≤ C_{U_{2}}(f) ≤ O(n2^{n})

Proof:

The function f can be written in its DNF as:

F (x_{1}, …, x_{n} = ∨_{f(α_{1},...,α_{n})=1}x_{1}^{α_{1}} · · · · · x_{n}^{α_{n}}  (2.1)

This can be implemented by a U_{2}-circuit of size O(n2^{n}), and depth 2.

2.1.2 A Better Upper Bound: O(2^{n})

Claim 2.3 C_{B_{2}}(B_{n}) ≤ O(2^{n})

Proof:

Every f ∈ B_{n} can be written in the following form:

f(x_{1}, …, x_{n}) = (x_{1} ∧ f(1, x_{2}, …, x_{n})) ∨ (\overline{x_{1}} ∧ f(0, x_{2}, …, x_{n}))  (2.2)

So we can compute f using two B_{n−1} functions and three B_{2}-functions. We can continue recursively, and build the Boolean circuit that computes f, which is a tree of size C_{n} (as in figure 2.1). Trivially C_{2} = 1 and C_{n} = 2C_{n−1} + 3, hence C_{n} = 2^{n} − 3.

x_{2} \overline{x_{2}}  x_{2} \overline{x_{2}} ∧  ∧  ∧  ∧ ∧ ∧ ∨  ∨ ∨ x_{1}  \overline{x_{2}}

Figure 2.1: The tree computing f using AND and OR gates

Remark:

We can reduce the multiplicative factor, expressing f as:

f(x_{1}, …, x_{n}) = f(0, x_{2}, …, x_{n}) ⊕ (x_{1} ∧ (f(1, x_{2}, …, x_{n}) ⊕ f(0, x_{2}, …, x_{n})))  (2.3)

Construction of the proper tree (as in figure 2.2) yields C_{n} = 2C_{n−1} + 2 and C_{n} = \frac{3}{4} · 2^{n} − 2.

Definition

A formula is a circuit in which the fan-out degree of every vertex, except the output vertex, is exactly one (i.e the circuit is a tree, rooted at the function output).

Definition

Let f be a Boolean function, and let Ω be a base. Then L_{Ω}(f) is the size of the minimal formula over Ω which computes f.

Surely C_{Ω}(f) ≤ L_{Ω}(f). The above circuits are formulas. There are several reasons for restricting ourselves to formulas:

• It is easier to get results, for instance, there are known non-linear lower bounds for sizes of formulas computing problems in NP, but no such bounds are known for general circuits.

∧

+

x

variables

variables

n − 1

n − 1

Figure 2.2: The tree computing f using XOR and AND gates

• There is a connection between the formula size and the depth of functions - we shall see that: D_{Ω}(f) = Θ(log(L_{Ω}(f))).

2.1.3 Improving the Bound to O(\frac{2^{n}}{n})

Claim 2.4 C_{B_{2}}(B_{n}) ≤ O(\frac{2^{n}}{n})

Proof:

Let’s take a look at the tree we have constructed. For each 0 < k < n, the bottom k levels of this tree consist of 2^{n−k} sub-trees of depth k, each computing a Boolean function of k variables. (see figure 2.3). However, there are only 2^{2^{k}} such functions. We can construct a circuit that computes all the functions of k bits, and use the output of this construction for the top n − k levels in our tree. We shall prove computation of all the functions of k bits, can be done using only (1 + o(1))2^{2^{k}} gates:

Assume, by induction, that we have constructed a circuit which computes all the (k − 1)- bit functions using (1+o(1))2^{2^{k−1}} gates. Let x_{k} be a new variable. According to equation 2.3, each k-bit function is a XOR gate with one enrty which is a (k − 1)-bit function, and with a second enrty which is the output of an AND gate, between x_{k} and some (k − 1)-bit function (see figure 2.4). We need to add 2^{2^{k−1}} AND gates, and 2^{2^{k}} XOR gates, to the existing (1 + o(1))2^{2^{k−1}} gates. Hence, we need a total of (1 + o(1))2^{2^{k}} gates to compute all the functions of k bits.

According to the arguments above, we can compute every f ∈ B_{n} using O(2^{n−k} + 2^{2^{k}}) gates. We can choose k ≈ log(n − log n), and get a total of O(\frac{2^{n}}{n}) gates.

Top n − k levels Bottom k levels  2^{n−k} subtrees

Figure 2.3: The k bottom levels consist of 2^{n−k} sub-trees of depth k

∧  ∧  ∧ appropriate pairs compute all (k − 1)-bit functions 2^{2^{k}} XORs between 2^{2^{k}} outputs 2^{2^{k−1}} outputs  x_{1}  x_{2}  x_{k−1} x_{k}

Figure 2.4: Computing all 2^{2^{k}} k-bit functions

2.1.4 Eliminating the Multiplicative Constant

Theorem 2.5 (Lupanov) C_{B_{2}}(B_{n}) = (1 + o(1)) · \frac{2^{n}}{n}

Proof:

Let f : {0, 1}^{n} → {0, 1}. be a Boolean function. Let M be the 2^{k} × 2^{n−k} truth matrix of f, i.e. for each x_{1}, …, x_{n} ∈ {0, 1}, the value of f(x_{1}, …, x_{n}) will be written in the row and column whose indices, in binary notation, are x_{1}, … x_{k}, and x_{k+1}, …, x_{n}. Let s be an integer, 1 ≤ s ≤ 2^{k}, and let p = ⌈\frac{2^{k}}{s} ⌉. We shall divide M into p horizontal stripes, A_{1}, …, A_{p}, where A_{i}, for i = 1, … p − 1, consists of the s rows of M, ending at the s · i’th row, and A_{p} consists of the last s′ ≤ s rows of M (see figure 2.5).

For each i, 1 ≤ i ≤ p, and for each word w = w_{1}w_{2} … w_{s} ∈ {0, 1}^{s}, we define a function g_{iw} : {0, 1}^{k} → {0, 1}. Let x′ be the number whose binary representation is x_{1}, …, x_{k}, and let x′′ = x′ − (i − 1)s. Define the value of g_{iw}(x_{1}, …, x_{k}) to be as follows (see figure 2.6):

• If 1 ≤ x′′ ≤ s, then define g_{iw}(x_{1}, …, x_{k}) = w_{x′′}.

• Otherwise define g_{iw}(x_{1}, …, x_{k}) = 0.

Note that the g_{iw}’s are independent of the truth matrix M.

For each i, 1 ≤ i ≤ p, and for each word w = w_{1}w_{2} … w_{n} ∈ {0, 1}^{s}, we define a function h_{iw} : {0, 1}^{n−k} → {0, 1}. Let x be the number whose binary representation is x_{k+1}, …, x_{n}. Define the value of h_{iw}(x_{k+1}, …, x_{k}) to be as follows:

00  0 0 0 1 0 10 00 0 1 1  1  111  ss s′ A_{1} A_{2} A_{p} 2^{n−k}  2^{k} x_{k} x_{k+1} x_{n} x_{1}

Figure 2.5: The matrix M and its division to stripes

000 00  0 0 0 11 1  1  w A_{i} A_{2} A_{1} x_{1}  x_{k}

Figure 2.6: The function g_{iw} • If the word w is written in the x’th column of the stripe A_{i}, then define h_{iw}(x_{k+1}, …, x_{n}) = 1.

• Otherwise define h_{iw}(x_{k+1}, …, x_{n}) = 0.

00  0 0 0 1 0 10 00 0 1 1  1  111 00 0  0 0 0 w  w  w x_{1}  x_{k} x_{k+1} x_{n}  A_{i}

Figure 2.7: The truth matrix of g_{iw}(x_{1}, …, x_{k}) ∧ h_{iw}(x_{k+1}, … x_{n})

We can see that the truth matrix of g_{iw}(x_{1}, …, x_{k})∧h_{iw}(x_{k+1}, … x_{n}) equals M in every entry which is in a word w that is written in the stripe A_{i}. Otherwise, g_{iw}(x_{1}, …, x_{k}) ∧ h_{iw}(x_{k+1}, … x_{n}) = 0 (see figure 2.7). Hence:

f(x_{1}, …, x_{n}) = ∨_{i,w}(g_{iw}(x_{1}, …, x_{k}) ∧ h_{iw}(x_{k+1}, … x_{n}))  (2.4)

We shall compute all the g_{iw}’s and the h_{iw}’s using their DNF , and then use equation 2.4 for computing f:

Level 1: Compute all the 2^{k} monoms of the k variables x_{1}, …, x_{k}, and all the 2^{n−k} monoms of the n − k variables x_{k+1}, …, x_{n−k}. These constructions can be performed recursively using O(2^{k}) and O(2^{n−k}) gates, respectively.

Level 2: Compute g_{iw} and h_{iw}, using their DNF , for each i = 1, … p and for each word w ∈ {0, 1}^{s}:

– Every monom x_{1}^{α_{1}} ·· · ··x_{k}^{α_{k}} participates in the DNF of no more than 2^{s−1} functions g_{iw}, because g_{iw}(α_{1}, … α_{k}) = 1 forces a single value of i, and a certain bit in w to be 1.

– Every monom x_{k+1}^{α_{k+1}} · · · · · x_{n}^{α_{n}} participates in the DNF of exactly p functions h_{iw}, which are h_{iw_{i}}, where w_{i} is the word written in A_{i}, in the α’th column (where α’s binary notation is α_{k+1}, … α_{n}.

Hence this level requires O(2^{s−1} · 2^{k} + p · 2^{n−k}) ≤ O(2^{k+s} + \frac{2^{n}}{s}) gates.

Level 3: Compute g_{iw} ∧ h_{iw} for each i = 1, … p, and for each w ∈ {0, 1}^{s}. This level requires p · 2^{s} ≤ \frac{2^{k+s}}{s} gates.

Level 4: Compute the disjunction of all the outputs of the previous level, according to equation 2.4. This level requires p · 2^{s} − 1 ≤ \frac{2^{k+s}}{s} gates.

Hence, the total number of gates needed is O(2^{k} + 2^{n−k}) + 2^{k+s} + \frac{2^{n}}{s} + \frac{2^{k+s+1}}{s}. Choosing s ≈ n − 5 log n and k ≈ 3 log n leaves us with O(n^{3} + \frac{2^{n}}{n^{3}} ) + O(\frac{2^{n}}{n^{2}} ) + (1 + o(1))\frac{2^{n}}{n−5 log n} + O(\frac{2^{n}}{n^{2}(n−5 log n)}) = (1 + o(1))\frac{2^{n}}{n}.

2.1.5 Implications to U_{∞}

Definition Let U_{∞} be the set of all functions (x_{1}^{a_{1}} ∧…∧x_{n}^{a_{n}})^{b}, for any n > 1 and a_{1}, …, a_{n}, b ∈ {0, 1}.

In theorem 2.5, we have constructed a circuit, which is of depth four when using ∨ and ∧ gates of unbounded fan-in ^{1}. To implement this circuit using U_{∞}-gates we shall need:

Level 1: 2^{k} + 2^{n−k} gates.

Level 2: \frac{2^{k+s+1}}{s} gates (one for each g_{iw} and h_{iw}).

Level 3: \frac{2^{k+s}}{s} gates.

1We disregard the negation gates which are applied to the variables. These can be considered to be a zero level

Level 4: one gate.

The number of gates is monotonically increasing in s, therefore we shall choose s = 1 to get O(2^{k} + 2^{n−k}) gates. This is minimized to O(2^{\frac{n}{2}} ) by choosing k ≈ \frac{n}{2}. This is much better than, for instance, the DNF construction, which implements every f ∈ B_{n} using 2^{n} U_{∞}-gates. The tradeoff is the increase in the depth of the circuit from two in the DNF construction, to four in this construction.

However, it seems that the third level of our construction is inefficient over U_{∞}, because it uses only U_{2}-gates, not utilizing the possible unbounded fan-in. Indeed, if we use CNF constructions instead of DNF constructions of the g_{iw}’s and the h_{iw}’s (in the first two levels), then level 3 can be merged into level 2.

Corollary 2.6 Every f ∈ B_{n} can be computed using a U_{∞}-circuit of size O(2^{\frac{n}{2}} ) and of depth three.

Exercise:

Prove, by counting arguments, that computing almost every function in B_{n} using U_{∞}- gates requires a circuit of size Ω(2^{\frac{n}{2}} ). (In fact, computing almost every function in B_{n} using U_{∞}-gates requires a circuit of size Ω(2^{\frac{n}{2}} ) and of depth three).

2.2 Linear Lower Bounds

2.2.1 Introduction

As we have seen, the Boolean complexity of an arbitrary Boolean function is known with a surprising accuracy. We have great interest in efficient computing of specific functions, like:

• The majority of n bits.

• The multiplication of two n-bit binary numbers.

• Is there a perfect matching in the graph encoded by an n × n adjacency matrix?

• Is there a Hamiltonian path in the graph encoded by an n × n adjacency matrix?

We would also like to prove lower bounds on circuits that compute NP problems, since there is a tight connection between Turing-machines and Boolean circuits: The existence of a polynomial time Turing-machine implies the ability of constructing a sequence of polynomial size circuits (one for each length of input)

Unfortunately, the best known lower bound for any specific NP function is only linear: 3n over B_{2} by N.Blum, and 4n over U_{2} by U.Zwick.

2.2.2 A Lower Bound for T_{k}^{n}

Definition

For each k, n, define the threshold function, T_{k}^{n} : {0, 1}^{n} → {0, 1} for every x_{1}, …, x_{n} ∈ {0, 1} to be as follows:

• If Σ_{i=1}^{n}x_{i} ≥ k, then T_{k}^{n}(x_{1}, …, x_{n}) = 1.

• Otherwise T_{k}^{n}(x_{1}, …, x_{n}) = 0.

Theorem 2.7 For each 2 ≤ k ≤ n − 1, there exists: C_{B_{2}}(T_{k}^{n}) ≥ 2n − 4.

Proof: We shall prove the theorem by induction over n, using the proof technique of gate elimi-

nation.

base: For n = 3 we have only k = 2. This function depends on all its inputs, therefore, according to a theorem stated in the previous lecture, C_{B_{2}}(T_{2}^{3}) ≥ 2.

step: Assume correctness for every i < n, n ≥ 4. We shall prove correctness for n. Let us examine a circuit G that computes T_{k}^{n}. There is a gate A, whose two entries are variables (for instance, the first gate in the topological sort of G). W.l.o.g., let the two entries be x_{1} and x_{2} respectively. Assigning the four possible binary combinations to x_{1} and x_{2}, yields three different restrictions of T_{k}^{n} to the variables x_{3}, …, x_{n}, which are T_{k}^{n−2}, T_{k−1}^{n−2}, T_{k−2}^{n−2}. The output of A, however, has only 2 possible values, therefore at least one of the variables x_{1}, x_{2} is an input of some other gate B ≠ A. W.l.o.g., let x_{1} be the common input of A and B, and let y be the other input of B, which is not necessarily a variable (see figure 2.8). The gate A depends solely on x_{1} and x_{2}, hence A’s output is not the output of G. If B’s output is the output of G, then y may not be a variable.

Any assignment of a value to x_{1}, restricts A and B to single variable functions: a constant 0, a constant 1, identity, or negation. In any case, after an assignment of a value α ∈ {0, 1} to x_{1}, A and B can be removed from the new circuit G_{α}, where the only need for further change whould be, perhaps, to negate x_{2} or y. This negation can be done without adding gates, at the gates that x_{2} and y are input to, or, if y is G’s output, at the gate that y is an output of. The circuit G_{α} computes the restriction of T_{k}^{n} to the variables x_{2}, …, x_{n}, which is T_{k−α}^{n−1}. There are two cases:

k = 2 In this case, let α = 0.

k > 2 In this case, let α = 1.

B  A x_{1}  x_{2} y  0/1/y/\overline{y}  0/1/x_{2}/\overline{x_{2}} Figure 2.8:

In both cases, 2 ≤ k − α ≤ n − 1, therefore, by our inductive hypothesis, G_{α} has, at least, 2(n − 1) − 4 gates, therefore G has, at least, 2n − 4 gates.

2.2.3 A Lower Bound for XOR_{n}

Theorem 2.8 C_{U_{2}}(XOR_{n}) = 3(n − 1)

Proof:

⇒ We can construct one XOR gate using three U_{2}-gates (as in figure 2.9), because:

x ⊕ y = (x ∧ \overline{y}) ∨ (\overline{x} ∧ y)  (2.5)

And we can construct the XOR_{n} function using n − 1 XOR gates, because trivially XOR_{2}(x, y) = x ⊕ y, and XOR_{n}(x_{1}, …, x_{n}) = XOR_{n−1}(x_{1}, …, x_{n−1}) ⊕ x_{n}.

⇐ We shall prove the lower bound by induction over n, using the proof technique of gate elimination.

base: For n = 2 we need at least three gates, because one gate is not enough (XOR_{2} ∉ U_{2}), and suppose to the contrary that XOR_{2}(x, y) can be implemented using two U_{2}- gates, the gate A and the gate B, then w.l.o.g. x and y are entries to B, while x and B(x, y) are entries to A (as in figure 2.10). Then since A ∈ U_{2}, there exists a value α ∈ {0, 1} whose assignment to x determines the output of A, which is the output of the circuit. This contradicts the definition of XOR_{2}.

+  ∨ ∧  ∧ x  y  x  \overline{y}  \overline{x}  y

Figure 2.9: Construction of XOR using three U_{2}-gates

y  A  xB  x

Figure 2.10: It is impossible to compute XOR using two U_{2}-gates step: Assume correctness for every i < n, n ≥ 3. We shall prove correctness for n. Let

us examine a minimal size circuit G that computes XOR_{n}. There is a gate A, whose two entries are variables (for instance, the first gate in the topological sort of G). W.l.o.g., let the two entries be x_{1} and x_{2} respectively. Since there exist an assignment to x_{2} that determines the output of the gate A, and since no such assignment restricts XOR_{n} to a function x_{1}, x_{3}, x_{4}, …, x_{n} which is independent of x_{1}, Then x_{1} is an input of some other gate B ≠ A. Let y be the other input of B (not necessarily a variable). The output of A depends solely on x_{1} and x_{2}, hence A’s output is not the output of G. If B’s output is the output of G, then y may not be a variable.

y  A B  x_{1}  x_{2}

Figure 2.11: If A feeds only B, the circuit is not minimal

We shall see that y is not the only output of A. Suppose, to the contrary, that y is the sole output of A (like in figure 2.11). Then the output of B is the B_{2}-function D(x_{1}, x_{2}) = B(x_{1}, A(x_{1}, x_{2}). We have already proven that such a formula cannot implement XOR_{2} (or \overline{XOR_{2}}), therefore D is either constant, or a single variable function, or in D ∈ U_{2}. In any case, the gates A and B can be replaced by one U_{2}-gate, without changing the function that G implements, contradicting G’s minimality. Hence, y is not the only output of A. According to the above, there exists a gate C ≠ A, B in G, such that A’s output is an input to C. Let z be the second input to C, as in figure 2.12. If B’s output is the output of G, then y may not be a variable. If C’s output is the output of G, then z may not be a variable. Since A ∈ U_{2}, there exist an assignment α ∈ {0, 1} to x_{1}, which determines the output of A. By this assignment, B and C are restricted to single variable functions. In any case, after an assignment of the value α to x_{1}, the gates A, B, and C can be removed from the new circuit G_{α}, where the only need for further change whould be, perhaps, to negate y or z. This negation can be done without

B  A  C y  x_{1}  x_{2}  z 0/1/y/\overline{y}  0/1/z/\overline{z} 0/1

Figure 2.12: The gates A, B, and C

adding gates:

∗ If the output of B is the output of G, then y can be negated at the gate that y is an output of. Otherwise, y can be negated at the gate y is an input to.

∗ If the output of C is the output of G, then z can be negated at the gate that z is an output of. Otherwise, z can be negated at the gate z is an input to.

The circuit G_{α} computes the restriction of XOR_{n} to the variables x_{2}, …, x_{n}, which is XOR_{n−1} or \overline{XOR_{n−1}}. Therefore, by our inductive hypothesis, G_{α}, perhaps negated, has, at least, 3(n − 2) gates, therefore G has, at least, 3(n − 1) gates.