Boolean Circuit Complexity Fall Semester, 1994-5

Lecture 4: November 17

Lecturer: Uri Zwick Scribe: Shimon Shahar

4.1 Arithmetic Operations

4.1.1 Division

In the previous lesson we have discussed in detail addition and multiplication circuits. The following theorms about division circuits will complete the subject.

Theorem 4.1 (Reif, Tate) There exist division circuits of size O(n log n log log n) and depth O(log n log log n). Moreover these circuits are log-space uniform.

Theorem 4.2 (Beame, Cook, Hoover) There exist division circuits of polinomial size, and depth O(log n).

The question whether division is in NC^{1} (i.e., whether there are log-space uniform division circuits of depth O(log n) ) is still open.

4.2 Formulae

Definition A formula is a circuit in which the fan-out of every vertex, except the output vertex, is exactly one. A formula, in other words, is a circuit whose underlying graph is a tree. The size of a formula is the number of leaves in it, and the depth of a formula is the length of the longest path in it.

Remark: For any finite basis Ω, the number of gates in a formula is proportional to the number of leaves in its tree.

Definition Let f be a Boolean function and let Ω be a basis. Then, the formula complexity of f over Ω, L_{Ω}(f), is the minimum number of occurences of variables and their negations in a formula over Ω that computes f.

Definition Let f be a Boolean function and let Ω be a basis. Then, the depth of f over Ω, D_{Ω}(f), is the minimum depth of a formula over Ω that computes f.

Claim 4.3 If a Boolean function f can be computed by a circuit of depth d, then it can also be computed by a formula of depth d.

Proof: Given a circuit C which computes the function f, we shall build a simulation circuit F as follows. The circuit C can be divided into levels, in each level all the gates have the same minimal distance from the output gate. We will use an inductive process, in each step we build a circuit F_{i} which computes f correctly, and all the gates in the lowest i levels have fan-out one.

The induction basis: the lowest level, which contain variables. In that level there is nothing to do, so F_{0} is equal to C.

The induction step: If a gate A in level d − i has fan-out k in C, then in F_{i} we construct k copies of the part of the circuit whose its output gate is A (denoted A_{j}). After we do that all the gates in that level will have fan-out one. For each gate in C whose input was A, we use A_{j} in the new circuit F_{i}. Using the induction hypothesis, we conclude that in F_{i} all gates in the lowest i levels, have fan-out one. We also conclude that F_{i} computes f correctly. In each step the depth of the circuit remains the same, so F_{d} is a formula for f with the same depth.

The recursive process described in the proof of the claim guarenties the same depth for both circuits, but it does not guarenty anything regarding to the size of the new circuit. The question whether there is a function f for which there exists a circuit of polynomial size but no formula of polynomial size is still open.

Claim 4.4 For any Boolean function f, D_{B_{2}}(f) = Ω(log L_{B_{2}}(f)).

Proof: Trivial, from the fact that any formula circuit is a tree. If the basis is B_{2}, then the formula is a binary tree. Therefore the number of the leaves of the tree (the size of the formula), is at most exponential in the depth depth of the tree (the circuit depth).

Claim 4.5 For any Boolean function f, D_{B_{2}}(f) = O(log L_{B_{2}}(f)).

Proof: In order to prove the claim, we first have to prove a lemma about binary trees.

If T is a tree, we let |T | be the number of leaves in T. If x is a node of T, we let T_{x} be the subtree of T rooted at x.

Lemma 4.6 Let T be a binary tree with n leaves and let m be a real number, 1 ≤ m < n. Then there exists a node x, with two children x_{1}, x_{2}, such that |T_{x}| ≥ m but |T_{x_{1}}|, |T_{x_{2}}| < m.

Proof: The proof uses induction on the number of tree levels. We start with the root. If the claim in the lemma is true for the root, then we are done. Otherwise, the root has at least one child with more than m leaves in its subtree. Now we can use the same argument for the subtree rooted at this child. Due to the finite number of levels in the tree, the process is bound to stop after a finite number of steps.

A  A  X A The original circuit X 1 The transformed circuit 0 2 → 1

Figure 4.1: The modification step of the circuit in claim 4.5 .

From this lemma we can conclude that there exists a node x, for which there are more than \frac{n}{3} but less than \frac{2n}{3} leaves in its subtree, because both its children have less than \frac{n}{3} leaves in their subtrees. Moreover we conclude that there exists an edge e whose removal from the tree seperates the tree into two trees with less than \frac{2n}{3} leaves in each (e is the edge which connects x to its parent). Using this conclussion we are now ready to prove the theorm. Suppose we have formula of size n. Then, there exists a gate x that if we remove from the circuit we obtain two formulae of size less than \frac{2n}{3}. In order to reduce the depth of the circuit we replace it with three circuits. The first circuit computes the original tree that above x, assuming x is 0. The second circuit does the same, but assumes x is 1. The third circuit compute the subtree of x. We combine the circuits using a 2 → 1 selector. The construction is described in Figure 4.1. Let D(n) be the maximal depth of a function whose formula size is at most n. This process defines a recursive method from which we obtain the following recursive equations:

• D(n) ≤ D(⌊\frac{2n}{3}⌋) + 2

• D(2) = 1

Solving the equations we obtain : D(n) ≤ 2 log_{\frac{3}{2}} n ≈ 3.42 log n. The constant 3.42 was reduced to 2.47 for B_{2} (Brent), and to 1.73 for U_{2} (Khrapchenko).

From both claims we obtain the following theorm.

Theorem 4.7 For any finite basis Ω, and for any Boolean function f, Θ(D_{Ω}(f)) = log L_{Ω}(f).

Proof: The previous two claims prove the theorm for B_{2}. For any finite basis Ω, there exists a k such that any gate from Ω has less than k inputs. Therefore a formula over Ω will be a k-ary tree, and we can prove similar claims to 4.4 and 4.5 for k-ary trees.

4.3 Lower bounds for formulae

4.3.1 Nečiporuk’s lower bound

Definition Let f : {0, 1}^{n} → {0, 1} be a Boolean function of n variables and let V be a subset of its variables. A restriction of f over V is a function obtained by assigning values to all variables not in V. The number of all possible restrictions for a function f over V is denoted by r_{V} (f).

Theorem 4.8 (Nečiporuk 1966) For any finite basis Ω there exists a constant c_{Ω} such that for any Boolean function f : {0, 1}^{n} → {0, 1}, and for any partition V_{1}, V_{2}, …, V_{p} of its variable set, the following condition holds:

L_{Ω}(f) ≥ c_{Ω}Σ_{i=1}^{p} log r_{V_{i}}(f)

Before we prove the theorm we bring an example of Paul to demonstrate its use.

Definition The indirect storage access function is defined as follows:

f : {0, 1}^{2n+log n−log log n} → {0, 1}

Where its variables set is divided to three blocks:

A = {a_{1} … a_{log n−log log n}}

X = {x_{1} … x_{n}}

Y = {y_{1} … y_{n}}

and f = Y [X[A]].

Which means: suppose that the number written in the block A is j in a binary representation, if we divide the block X into sets of log n bits each, denoted X_{i}. j can be treated as an index number of a set in X. The number written in that set can be treated as an index of a bit in Y. The result of f is the value of the bit chosen from Y.

For example: if n = 16 then |A| = 2 and both |X|, |Y | = 16, Suppose A = 01, X = 1011 1001 0101 0010, and Y = 1011101000110100. We compute f as follows: the number in A is 1, which means we take the second group of bits from X (the first group will be taken if A = 0). The number written in that group is 1001 which is 9, therefore the value of f is the value of the tenth bit from Y, which is 0.

Claim 4.9 There exists a formula for the indirect storage access function of size O(\frac{n^{2}}{log n}). There also exists a circuit for the indirect storage access function of size O(n).

Proof: We can easily implement the function using two levels of selectors. The lower level consists of log n selectors [\frac{n}{log n} → 1]. They use A as control bits, and X_{(i−1) log n+j} as the input bits for the selector number j, where i = 1 … \frac{n}{log n}. Therefore the output of all selectors will be the bits in the i-th set of X. These bits will be used as control bits for the higher level, which is an [n → 1] selector. The circuit is shown in Figure 4.2. Next we describe an implementation of an [n → 1] selector. We describe the implementation recursivly.

Induction basis: a [2 → 1] selector (shown in Figure 4.3).

The induction step: We build an [n → 1] selector using two [\frac{n}{2} → 1] selectors, and a [2 → 1] selector, as (described in Figure 4.4). Let L(n) be the size of the formula of an [n → 1] selector.

This implementation leads to the following recursive equations:

L(2) = 4

L(n) = 2L(\frac{n}{2}) + 2

Solving these equations we obtain:

L(n) = 3n − 2.

In the circuit we use each control bit more than once. The first control bit a_{0} appears twice, the second control bit a_{1} appears four times, and so on (the last control bit a_{log n} appears n times).

Therefore, the size of the circuit will be: 2n\frac{3n}{log n} + 3n − 2 = O(\frac{n^{2}}{log n}).

n → 1 a_{k}  a_{k}  a_{k}  y_{n} x_{n} x_{1} a_{1}  a_{1}  a_{1} x_{log n}  y_{1} x_{2} x_{n−logn+1}  x_{n−log n+2}

Figure 4.2: An implementation of the indirect storage access function.

X_{0}  \overline{A} X_{1}  A

Figure 4.3: 2 → 1 selector .

\frac{n}{2} → 1  a_{n} a_{n} a_{1}  2 → 1 a_{1}  \frac{n}{2} → 1 a_{0} x_{0}  x_{\frac{n}{2}−1}  x_{n−1} x\frac{n}{2}

Figure 4.4: n → 1 selector .

Claim 4.10 The size of any formula which computes the indirect storage access function is Ω(\frac{n^{2}}{log n}).

Proof: We choose to divide the set of variables of f such that every block X_{i} is in a seperate set. For each block X_{i} there are at least 2^{n} different restrictions, because if we choose A to be i, we can write in Y, any Boolean number of n bits. Therefore using Nečiporuk’s theorm we obtain: L_{Ω}(f) ≥ c_{Ω}(\frac{n}{log n} log 2^{n}) = Ω(\frac{n^{2}}{log n})

From both claims we conclude that the formula size of the indirect storage access function is Θ(\frac{n^{2}}{log n}). Exercise 1: Implement a [n → 1] selector with a circuit of size: 2n + O(\sqrt{n}). Exercise 2: Implement a [n → 1] selector with a circuit of depth log n + O(log log n).

Claim 4.11 For any two finite bases Ω_{1}, Ω_{2}, and for any function f

L_{Ω_{1}}(f) = L_{Ω_{2}}^{O(1)}(f)

Proof: Trivial, because D_{Ω_{1}}(f) = O(D_{Ω_{2}}(f)), and for any basis Ω, D_{Ω}(f) = Θ(log L_{Ω}(f)).

Exercise 3: Show that the lower bound obtained by using Nečiporuk’s bound, is always O(\frac{n^{2}}{log n}).

Hint: Use the fact that r_{V} (F) ≤ 2^{n−k} and r_{V} (f) ≤ 2^{2^{k}} where k = |V |.

Proof:(Nečiporuk) Let T be a formula of minimal size for f. We let l_{i} be the number of leaves in T which are labeled by variables from V_{i}.

- A Combinator. - A Variable from Vi - A Controller  - An edge on the path of Xi - An essential edge

Figure 4.5: The formula in Nečiporuk’s theorm.

Due to the minimality of T, L_{Ω}(f) = |T | = Σ_{i=1}^{p}l_{i}. For any finite basis Ω, there is a k such that Ω ⊆ B_{k}. We try to find the number of restrictions for the set V_{j}.

In Figure 4.5, we can see the tree that represents T.

An essential edge is an edge on a path from a variable in V_{j} to the root.

The black nodes (combinators) are gates that at least two of their inputs are essential.

The gray nodes (controllers) are gates that one of their inputs is essential.

The hollow nodes are variables.

For any controler, if the input is g, then the output is ag ⊕ b, for some a, b ∈ {0, 1}, therefore the output of any sequence of controllers, will be of the same form.

The number of combinators in the tree is bounded in l − 1. The number of controler chains in the tree is bounded in 2l − 1 (the number of the leaves, plus the number of the controlers).

Any substitution for the variables not in V_{j}, will determine the functions that the controlers and the combinators will compute. In any combinator there are at most k −2 inputs that are independent of the variables of V_{j} (outputs of sub-circuiuts that do not include variables from V_{j} as inputs). These inputs determines the function of the controler. In the worst case all functions are different, therefore any controler can compute at most 2^{k−2} different functions. Any sequence of controlers can compute at most 4 different functions.

If we multiply all the possibilities we will obtain : r_{V_{j}}(f) ≤ 2^{(k−2)(l−1)}4^{2l−1} = 2^{(k+2)l−k}, which yields: log r_{V_{j}}(f)) ≤ (k + 2)l − k.

From this inequality we obtain an upper bound on r_{V_{i}}(f) in terms of the size l_{i} of the restricted formula. If we sum for all i, we obtain a bound on the size of the formula. The constant c_{Ω} depends on the basis (due to k).

The bound from Nečiporuk’s theorm, is the best lower bound known for formulae over B_{2}.

4.3.2 Lower Bounds for U_{2} Formulae

Theorem 4.12 (Khrapchenko (1972))

Let f : {0, 1}^{n} → {0, 1} be a Boolean function of n variables. Let A be a subset contained in f^{−1}(0), and B a subset contained in f^{−1}(1). Let c(A, B) = |{(x, y)|x ∈ A, y ∈ B, d_{H}(x, y) = 1}|. Where d_{H} is the Hamming distance. Then L_{u_{2}}(f) ≥ \frac{c(A,B)^{2}}{|A||B|}.

As for the previous theorm, we will first see some examples to demonstarte its use.

Example 1: f = x_{1} ⊕ x_{2} … ⊕ x_{n}. We chose A to be all the binary vectors V, for which f(V) = 0, and B to be the rest of the binary vectors. Then |A| = |B| = 2^{n−1}, and |C| = n2^{n−1} (for any vector from A, if we change one co-ordinate, we get a vector from B).

→ L_{u_{2}}(f) ≥ \begin{matrix}n^{2} & (2^{n−1})^{2} \\ (2^{n−1}) & ^{2} \end{matrix} = n^{2}

On the other hand the naive implementation yields O(n^{2}). Example 2: f = MAJ(x_{1}, x_{2} … x_{n}). We chose A to be all the binary vectors V, for

which exactly \frac{n−1}{2} components are 1, and B to be all the binary vectors V, for which exactly \frac{n+1}{2} components are 1 (assume n is odd).

Then |A| = |B| = \binom{n}{\frac{n−1}{2}}, and |C| = |A|\frac{n+1}{2} (for any vector from A, if we change one coordinate, we will get a vector from B).

→ L_{u_{2}}(f) ≥ (\frac{n+1}{2})^{2} = Ω(n^{2})