Boolean Circuit Complexity Fall Semester, 1994-5

Lecture 5: November 24

Lecturer: Uri Zwick Scribe: Dekel Tsur

5.1 Lower Bounds For de Morgan Formulae

5.1.1 Khrapchenko’s Lower Bound

Definition For two binary vectors x, y we define d_{H}(x, y) as the number of places in which x differ from y. For two sets of vectors A, B we define c(A, B) = {(x, y) : x ∈ A, y ∈ B, d_{H}(x, y) = 1}.

Theorem 5.1 (Khrapchenko 72) For any f : {0, 1}^{n} → {0, 1}, and any A ⊆ f^{−1}(0) and B ⊆ f^{−1}(1), we have L_{U_{2}}(f) ≥ \frac{[c(A,B)]^{2}}{|A||B|}.

Proof: For any function f there is a minimal formula T_{1} over U_{2} that computes it. If T_{2} is a minimal formula over {∧, ¬} that computes f, then |T_{1}| = |T_{2}|. We will show that for any minimal formula T over {∧, ¬} that computes a function f = f(T) and for any A ⊆ f^{−1}(0), B ⊆ f^{−1}(1) we have |T | ≥ \frac{[c(A,B)]^{2}}{|A||B|}. We will prove it using induction on the structure of T. The base of the induction is when |T | = 1, so f = x_{i} or f = \overline{x_{i}}. Since any x ∈ A and any y ∈ B participate in at most one pair in c(A, B), then c(A, B) ≤ |A|, |B|, therefore 1 ≥ \frac{[c(A,B)]^{2}}{|A||B|} as required. Suppose we proved for smaller formulas. There are two cases:

1. If T = ¬T′ , then |T | = |T′| and the claim is true.

2. T = T_{1} ∧ T_{2}. Since T is minimal, then T_{1}, T_{2} are also minimal. Let A ⊆ f^{−1}(0) , B ⊆ f^{−1}(1). We denote f_{1} = f(T_{1}) and f_{2} = f(T_{2}). Notice that B ⊆ f_{1}^{−1}(1), B ⊆ f_{2}^{−1}(1) and define B_{1} = B_{2} = B. Let A_{1} = A ∩ f_{1}^{−1}(0), A_{2} = A \ A_{1}. It is obvious that A_{1} ⊆ f_{1}^{−1}(0) and A_{2} ⊆ f_{2}^{−1}(0). Thus, by the induction hypothesis

|T | = |T_{1}| + |T_{2}| ≥ \frac{[c(A_{1}, B_{1})]^{2}}{|A_{1}||B_{1}|} + \frac{[c(A_{2}, B_{2})]^{2}}{|A_{2}||B_{2}|} .

Using the fact that c(A_{1}, B_{1}) + C(A_{2}, B_{2}) = c(A, B) and the following inequality:

∀x_{1}, x_{2}, y_{1}, y_{2} > 0 \frac{x_{1}^{2}}{y_{1}} + \frac{x_{2}^{2}}{y_{2}} ≥ \frac{(x_{1} + x_{2})^{2}}{y_{1} + y_{2}}

we get

|T | ≥ \frac{[c(A_{1}, B_{1}) + C(A_{2}, B_{2})]^{2}}{(|A_{1}| + |A_{2}|)|B|} = \frac{[c(A, B)]^{2}}{|A||B|} .

5.1.2 Subbotovskaya’s Lower Bound

Given a function f(x_{1}, …, x_{n}) we choose at random exactly m variables of f. For the other n − m variables we randomly assign a value of 0 or 1 with equal probabilities. We call the random set of choices a random restriction of f and denote it by ρ: {1, … n} → {0, 1, ∗}. We denote the resulting function by f_{ρ}.

It is obvious that for any base, E[L(f_{ρ})] ≤ \frac{m}{n}L(f). For B_{2}, for example, this inequality is tight (it can be shown by taking f = PARITY_{n} = x_{1} ⊕ x_{2} ⊕ ⋯ ⊕ x_{n}). However, for U_{2} we can give better results. Define Γ to be the supremum of all values for which E[L_{U_{2}}(f_{ρ})] = O((\frac{m}{n})^{Γ} L_{U_{2}}(f) + 1). Γ is called the shrinkage exponent of U_{2} formulas. We will later prove that Γ ≥ 1.5. It is easy to see by looking at PARITY_{n} that Γ ≤ 2. Hastad showed that Γ = 2.

Lemma 5.2 (Subbotovskaya 61) Let be f : {0, 1}^{n} → {0, 1} with L_{U_{2}}(f) > 1, and ρ be a random restriction that assign a value to exactly one variable. Then,

E[L_{U_{2}}(f_{ρ})] ≤ (1 − \frac{3}{2n}) L_{U_{2}}(f) .

Proof: Look at a minimal formula T for f. We go over all the variables and assign to each one the values 0 and 1. Let x be any variable. We look at all the leaves in the formula where x or \overline{x} appears. We denote by x^{i} the i-th leaf marked by x or \overline{x}, by g^{i} the gate to which x^{i} enters, and by N_{x}^{i} the other sub-formula that enters g^{i} (see figure 5.1).

Since the formula is minimal, all N_{x}^{i} are disjoint (if N_{x}^{i} ⊂ N_{x}^{j}, then there is a value b that assigning it to x^{i} will not change the function T computes, a contradiction). We denote f_{x←a} the restriction resulting from assigning the value a to the variable x.

For any i, assigning either 0 or 1 to x will delete the leaf x^{i} from the formula, and assigning the complement value to x will delete both x^{i} and N_{x}^{i} from the formula. In the first case we delete at least one leaf, and in the latter, at least 1 + |N_{x}^{i}| ≥ 2 leaves. Therefore ^{1}, (L(f) − L(f_{x←0})) + (L(f) − L(f_{x←1})) ≥ 3n_{x} where n_{x} is the number of leaves marked by x

1For brevity, we will sometimes write L(f) instead of L_{U_{2}}(f)

x^{1}  g^{1} N_{x}^{1}  x^{2}  g^{2} N_{x}^{2} Figure 5.1: N i x

or \overline{x}. Hence,

2nL(f) − ∑ ; \begin{matrix}1 ≤ i ≤ n \\ b ∈ \{0, 1\} \end{matrix}L(f_{x←b}) = ∑ ; \begin{matrix}1 ≤ i ≤ n \\ b ∈ \{0, 1\} \end{matrix}(L(f) − L(f_{x←b})) ≥ 3L(f)

and

E[L(f_{ρ})] = \frac{1}{2n} ∑ ; \begin{matrix}1 ≤ i ≤ n \\ b ∈ \{0, 1\} \end{matrix}L(f_{x←b}) ≤ \frac{1}{2n}(2n − 3)L(f) = (1 − \frac{3}{2n}) L(f) .

Corollary 5.3 (Subbotovskaya 61) Let f:{0, 1}^{n} → {0, 1} be a Boolean function, and let ρ be a random restriction that assigns a value to exactly one variable. Then,

E[L(f_{ρ}) − 1/3] ≤ (1 − \frac{3}{2n}) (L(f) − 1/3) .

Proof: If L(f) > 1 it is true by lemma 5.2. If L(f) = 1 then E[L(f_{ρ})] = 1 − 1/n and there is an equality, and it is also true when L(f) = 0.

Lemma 5.4 For any a ≥ 1 and m ≤ n, ∏_{k=m+1}^{n} (1 − \frac{a}{k}) ≤ (\frac{m}{n})^{a}.

Proof: Follows easily from the fact that for every a > 1 we have (1 − \frac{a}{k}) ≤ (1 − \frac{1}{k} )^{a}, and

the fact that ∏_{k=m+1}^{n} (1 − \frac{1}{k} ) = \frac{m}{n}.

Theorem 5.5 (Subbotovskaya 61) L_{U_{2}}(PARITY_{n}) = Ω(n^{1.5}).

Proof: By using lemma 5.2 on f = PARITY_{n}, we get E[L_{U_{2}}(f_{ρ})] ≤ (1 − \frac{3}{2n}) L(f). In

particular, there is a variable x_{i} and a value b such that L(f_{x←b}) ≤ (1 − \frac{3}{2n}) L(f). But since f_{x←b} is either PARITY_{n} or \overline{PARITY_{n}}, then

L(PARITY_{n−1}) ≤ (1 − \frac{3}{2n}) L(PARITY_{n}) .

By the induction hypothesis

L(PARITY_{1}) ≤ (1 − \frac{3}{2 · 2}) (1 − \frac{3}{2 · 3}) ⋯ (1 − \frac{3}{2n}) L(PARITY_{n})

and by using lemma 5.4 we get

L(PARITY_{n}) ≥ n^{1.5}L(PARITY_{1}) = n^{1.5} .

Theorem 5.6 (Subbotovskaya 61) Let f : {0, 1}^{n} → {0, 1} be a Boolean function, and let ρ:{1, … n} → {0, 1, ∗} be a random restriction that leaves exactly m live variables. Then,

E[L_{U_{2}}(f_{ρ})] ≤ (\frac{m}{n})^{1.5} L_{U_{2}}(f) + \frac{1}{3} .

Proof: Define a series of functions f = f_{n}, f_{n−1}, …, f_{m} where f_{k} obtained from f_{k−1} by assigning a random value to a single random variable. From corollary 5.3 we have

E[L(f_{k−1}) − 1/3] ≤ (1 − \frac{3}{2n}) (L(f_{k}) − 1/3) .

Hence

E[L(f_{m}) − 1/3] ≤ (1 − \frac{3}{2(m + 1)}) (1 − \frac{3}{2(m + 2)}) ⋯ (1 − \frac{3}{2(n)}) (L(f) − 1/3) ≤
≤ (\frac{m}{n})^{1.5} (L(f) − 1/3) .

y_{1} y_{2}  y_{n} n → 1^{\frac{n}{log n}} log n  Y  A_{n}(X, Y) X

Figure 5.2: The function A_{n}(x, y)

5.1.3 Andreev’s Lower Bound

Let us look at the following function:

A_{n}(X, Y) = Y_{∑_{i=0}^{log n−1}(⨁_{j=1}^{n/ log n} x_{ij})2^{i}}

In words, given two n-vectors X and Y we first split X into log n rows of n/ log n bits each, and calculate the parity of each row. Then we use the result as the address bits of a n → 1 selector that chooses which bit of Y to output. Look also at figure 5.2.

We will now show a lower bound

Theorem 5.7 (Andreev 85) L_{U_{2}}(A_{n}) = Ω(n^{2.5−o(1)}).

Proof: By setting the Y vector, the n→1 selector can calculate any Boolean function on its log n address bits. Using counting arguments, Shannon showed that for most functions of n variables, L_{U_{2}}(f) ≥ \frac{2^{n}}{log n}. In particular, there is a vector Y^{∗} for which the minimal formula for the function calculated by the selector has size of at least n/ log log n. We will look at the function A_{n}^{∗}(X) = A_{n}(X, Y^{∗}). We apply on A_{n}^{∗} a random restriction that leaves only m = 2 log n log log n variables alive. The probability that for a certain row of X there will be no live variable is at most (1 − \frac{1}{log n})^{m} < e^{−2 log log n} < (\frac{1}{log n})^{2}. Therefore, the probability that for any row of X there will be no live variable is less than \frac{1}{log n} < \frac{1}{2}. Hence,

\frac{1}{2} · \frac{n}{log log n} ≤ E[L(A_{n}^{∗}_{ρ_{m}})] ≤ (\frac{m}{n})^{1.5} L(A_{n}^{∗}) + \frac{1}{3}

and

L(A_{n}) ≥ L(A_{n}^{∗}) ≥ \frac{n}{2 log log n} (\frac{n}{2 log n log log n})^{1.5} = Ω (\frac{n^{2.5}}{(log n)^{1.5}(log log n)^{2.5})}) .

Note: Using the fact that Γ = 2, it can be shown that L_{U_{2}}(A_{n}) = Ω(n^{3−o(1)}). It is easy to see that L_{U_{2}}(A_{n}) = O(\frac{n^{3}}{log n}), so this lower bound is tight up to polylogarithmic factor.

5.2 Formula Complexity of Majority

For any complete base Ω, D_{Ω}(MAJ_{n}) = O(log n). Therefore, L_{Ω}(MAJ_{n}) = O(n^{c_{Ω}}). It can be shown that

L_{B_{2}}(MAJ_{n}) = O(n^{3.13}) and L_{B_{2}}(MAJ_{n}) = Ω(n log n) ,
L_{U_{2}}(MAJ_{n}) = O(n^{4.57}) and L_{U_{2}}(MAJ_{n}) = Ω(n^{2}) .

Since MAJ_{n} is a monotone function, the following question arises: Are there polynomial monotone formulae for MAJ_{n} ? ( a monotone formula is a formula over the base M_{2} = {∨, ∧}.)

A sorting network is a network made up from comparison units, where a comparison unit is a module whose two inputs are x and y and whose two ordered outputs are min{x, y} and max{x, y}. A sorting network has n inputs and n outputs which are the inputs sorted in increasing order. The depth of a sorting network is the length of the longest path from an input to an output.

Theorem 5.8 (AKS) There are sorting networks with depth O(log n).

When all the inputs are binary, a sorting network is a Boolean circuit, and it can be built over M_{2} since min{x, y} = x∧y and max{x, y} = x∨y. Moreover, by deleting all the outputs except the middle one, we get a circuit for MAJ_{n}. Therefore, by theorem 5.8 there is circuit over M_{2} with depth O(log n) for MAJ_{n}. From this, there are monotone formulae for MAJ_{n} of size O(n^{k}), when k is the coefficient hidden in the O(log n) of theorem 5.8. Unfortunately, the best upper bound on this coefficient, obtained by Paterson, is about 6000. We will obtain a better upper bound on the monotone formula complexity of the Majority function in the next lecture.