Boolean Circuit Complexity Fall Semester, 1994-5

Lecture 9: December 22

Lecturer: Uri Zwick Scribe: Ran Adler

9.1 Monotone vs. Non-monotone Circuit Complexity

9.1.1 Reminder

In the previous lecture we saw a exponential lower bound on the monotone complexity of the function CLIQUE_{k}(n). We obtained the Alon-Boppana result (1987):

C_{M_{2}}(CLIQUE_{k}(n)) = 2^{Ω(\sqrt{k})}

for k = O((\frac{n}{log^{2} n})^{\frac{1}{3}} ).

The CLIQUE problem is NP-Complete, and there are no known uniform or non-uniform polynomial size circuits to solve the problem. However, super-polynomial monotone lower bounds can be shown even on polynomial problems. Such a bound was obtained by Razborov for the Perfect Matching problem.

9.1.2 The Gap between Monotone and Non-monotone Complexities

Definition In an instance of the Perfect Matching problem (P M_{n}), ( \begin{matrix}n \\ 2 \end{matrix} ) Boolean values,

representing the edges of a graph on n vertices, are given. The value of P M_{n} is 1 for the given input, if an only if the corresponding graph has a perfect matching.

Theorem 9.1 (Razborov) C_{M}(P M_{n}) = n^{Ω(log n)}.

This shows a very large gap between monotone an general (non monotone) complexity, since there exists a polynomial time algorithm for the graph perfect matching problem, and hence: C(P M_{n}) = n^{O(1)}. Tardos strengthed this result:

Theorem 9.2 (Tardos)

The gap between C_{M} and C is exponential.

Tardos showed a function which obtains that gap. This function is related to the estimation of clique size, which is, as we have seen for the clique problem, hard to compute and to estimate.

9.1.3 Slice Functions

Unlike the previously mentioned functions, there is a class of functions for which the monotone complexity is very close to the general complexity:

Definition A function f : {0, 1}^{n} → {0, 1} is a slice function iff there exists a k such that the following hold:

∑_{i=1}^{n} x_{i} < k ⇒ f(x) = 0 ,

∑_{i=1}^{n} x_{i} > k ⇒ f(x) = 1 .

For a given f : {0, 1}^{n} → {0, 1}, the k^{th} slice of f, f^{(k)} is naturally defined as:

f^{(k)}(x) = \{ \begin{matrix}0 & ∑_{i=1}^{n} x_{i} < k \\ 1 & ∑_{i=1}^{n} x_{i} > k \\ f(x) & ∑_{i=1}^{n} x_{i} = k \end{matrix} .

Note that for any f, f^{(k)} is a monotone function.

Let us first show that hard functions have hard slices.

Claim 9.3 C(f) = C(f^{(0)}, f^{(1)}, … f^{(n)}) + O(n) ^{1} , Where C(f^{(0)}, f^{(1)}, … f^{(n)}) is the complexity of computing all the slice functions of f simultaneously.

Proof: We build a circuit for f from the circuit computing f^{(0)}, f^{(1)}, … f^{(n)}, see Figure 9.1. The n+1 outputs of the circuit are selected in an (n+1) → 1 MUX, which is connected to a circuit that computes the sum of the n bits. The complexity of the MUX and the summing circuit is, as shown in previous lectures, O(n).

Obviously C(f^{(0)}, f^{(1)}, … f^{(n)}) ≤ ∑_{i=0}^{n} C(f^{(i)}), so there exists a k ∈ {1, … n} such that:

C(f^{(k)}) ≥ \frac{C(f)}{n} − O(1)

1From here on, C means C_{B_{2}}, and C_{M} means C_{M_{2}}

n+1^{CNT}  ^{x_{1}} ^{x_{2}}  ^{x_{n}}^{x_{1}} ^{x_{2}}  ^{x_{n}}  ^{f^{(0)}}^{f^{(1)}}^{f^{(2)}}  ^{f^{(n)}} 1 →

Figure 9.1: A circuit for f using the circuit for f^{(0)}, f^{(1)}, … f^{(n)}

Now we show that the monotone complexity of slice functions is close to the general complexity of these functions. We begin with the following simple lemma.

Lemma 9.4 For every U_{2}-circuit β, there is an equivalent circuit, whose size is at most 2size(β), which uses NOT gates only on variables.

\overline{x}_{2} x_{1}  x_{3}  x_{1}  \overline{x}_{1} x_{2} \overline{x}_{2}  x_{3}  \overline{x}_{3}^{G_{1}}  ^{G_{2}}^{G_{3}}  ^{N_{1}}  ^{N′_{1}}^{N_{2}}  ^{N′_{2}}^{N_{3}}  ^{N′_{3}}

Figure 9.2: Creating the new circuit out of the original U_{2} circuit

Proof: Let G_{1}, G_{2}, … G_{|β|} be a topologically sorted list of the gates of the circuit. Let X̃ be the set of literals x_{1}, x_{2}, … x_{n}, \overline{x}_{1}, \overline{x}_{2}, … \overline{x}_{n}. Starting from G_{1}, we iteratively replace each gate G_{i} with 2 other gates, N_{i} and N′_{i}, that compute the original value of the gate, and the negated value. Assume G_{i} = (x^{a} ∧ y^{b})^{c}, where x and y are the inputs of the gate. Then N_{i} will compute x^{a} ∧ y^{b}, and N′_{i} will compute \overline{x^{a}} ∨ \overline{x^{b}}. See Figure 9.2 for an example.

Since the inputs of the original gate are variables in X̃, or outputs of previous gates in the list, we can replace x^{a}, x^{b}, \overline{x^{a}} and \overline{x^{b}} with the corresponding N_{j} or N′_{j}, or with variables in X̃. This completes the construction.

Theorem 9.5 If f is a slice function, then C_{M}(f) = O(C(f) + n^{2} log n)

Proof: Let β be a minimal U_{2} circuit for f. Using lemma 9.4 we get an equivalent circuit β′, which uses NOT gates only on variables.

∧ ∨ x_{1}x_{2} x_{n} \overline{x}_{1}\overline{x}_{2} \overline{x}_{n}

Figure 9.3: The new circuit with NOT gates only on leaves

The circuit β′ can be viewed as a monotone circuit, whose inputs are the literals x_{1}, x_{2}, … x_{n}, \overline{x}_{1}, \overline{x}_{2}, … \overline{x}_{n}. To build a monotone circuit on the original variables, we substitute monotone circuits for the negated variables, and claim that the new circuit is equivalent to the former (this is where we use the fact that f is a slice function). For each \overline{x}_{i} we substitute T_{k}^{n−1}(x_{1}, … x_{i−1}, x_{i+1}, … x_{n}) where T_{k}^{n} is the threshold function of n variables with threshold k.

T_{k}^{n−1}(x_{1}, … x_{i−1}, x_{i+1}, … x_{n}) = \{ \begin{matrix}0 & ∑_{j=1}^{n} x_{j} < k \\ 1 & ∑_{j=1}^{n} x_{j} > k \\ \overline{x}_{i} & ∑_{j=1}^{n} x_{j} = k \end{matrix}

Since β′ is monotone on the extended set of inputs, and since the computed function is a slice function, we get an equivalent circuit. Using a monotone circuit of size O(n log n) for T_{k}^{n−1}, the theorem follows.

9.2 Depth And Communication Complexity

In this section we introduce the notion Communication Complexity and show how it is related to the depth of Boolean formulae. This relation yields large lower bounds on the depth of monotone formulae.

Definition (Communication problem and communication complexity): Let A, B ⊆ {0, 1}^{n}, A ∩ B = ϕ. In the communication problem for A and B, there are two players, denoted by I and II. I and II know the sets A and B. These players are connected by a communication line. They use a communication protocol for communicating with each other.

I  II x  y communication

Figure 9.4: A Communication Problem

A protocol defines which player will be the first to send a bit, and, at any moment, given the value of the previously sent bits, it defines which player will send the next bit. The next player to send a bit is determined only by the bits which have already been sent. The protocol also defines when the conversation is ended.

In an instance of the problem, I is given x ∈ A, II is given y ∈ B, and they should agree upon an index i such that x_{i} ≠ y_{i}. (There exists at least one such index, as A ∩ B = ϕ and herefore x ≠ y). A protocol solves this problem if both players know the index i when the conversation is ended.

The Communication Complexity of the protocol is the largest number of bits that will be sent on the communication line for the given protocol for any pair x ∈ A and y ∈ B. The Communication Complexity of the problem, C(A, B), is the minimum of the Communication Complexity of all the protocols that solve it.

It is easy to see that for any A, B ⊆ {0, 1}^{n} we have C(A, B) ≤ n + log n, since the following protocol solves it:

• I sends the n bits of x to II

• II computes the desired index, and sends it to I

The bound can be improved to n + log^{∗} n, which is achieved by the following protocol:

1. If n = 1 then no communication is required.

2. I sends the first n − log n bits of x.

3. II sends to I the bit 1 if the n − log n it received coincide with the corresponding bits of y. Otherwise it sends 0, and then the log n bits of an index in which the vectors differ, and the protocol ends.

4. let n ← log n, and go back to (1).

For this protocol we get the recursive formula:

C(n) = n − log n + max{1 + log n, 1 + C(log n)}
= max{n + 1, n − log n + 1 + C(log n)}

Thus:

C(n) − n ≤ C(log n) − log n + 1.

This is the recursive formula of log^{∗} n so:

C(n) − n ≤ log^{∗} n.

Here are two examples:

Example 1: Let

A = {x ∈ {0, 1}^{n} | the number of 1′s in x is even }
B = {y ∈ {0, 1}^{n} | the number of 1′s in y is odd }

We show that C_{A,B}(n) ≤ 2 log n by showing a protocol which obtains this complexity. Later we will show that there is no better protocol. Here is the protocol: If the size of the problem (n) is 1, both players know the answer. Otherwise: I sends to II the XOR of the first \frac{n}{2} bits of x. II tells Iwhether it is equal to the XOR of the first \frac{n}{2} bits of y. Now both players can proceed on the proper \frac{n}{2} bits of their numbers which are known to be different. The recursion formula for this protocol, C(n) = 2 + C(\frac{n}{2}), yields the claimed result.

Example 2 (An Exercise): Let

A = {x ∈ {0, 1}^{n} | 3 divides the number of 1′s in x }
B = {y ∈ {0, 1}^{n} | 3 does not divide the number of 1′s in y }

If we use the approach of the previous solution (only that now I has to send the remainder modulo 3 of the number of bits), we get a 3 log n protocol, since now the remainder representation is 2-bits long. Chin improved this to 2.89 log n. Try to reconstruct his protocol

The following theorem shows the relation between formula depth and the communication complexity, as defined above:

Theorem 9.6 (Karchmer, Wigderson) For every boolean function f,

D_{U_{2}}(f) = C(f^{−1}(0), f^{−1}(1)).

Proof: First Direction: C(f^{−1}(0), f^{−1}(1)) ≤ D(f) We describe a protocol that solves the problem by sending at most D(f) bits, for every x and y. This protocol is determined by a minimaldepth Boolean formula for f. We may assume that the formula contains negations only on variables as we can repetitively apply De-Morgan’s rules, without changing the depth of the formula (and without making it longer), to obtain such a formula.

Suppose the root gate in the formula is an AND gate. Since the gate produces different value for x and y, we know that for y both sub-formulae return 1, and for x, at least one of the sub-formulae returns 0. In this case I will send II a bit, denoting a side where it gets 0.

Similarly, if the root gate is an OR gate, the player that gets 1 in one of the sub-formulae sends a bit, which represents the side of such a sub-formula.

After this bit has been sent, the two players can proceed on the corresponding subformula. After at most D(f) moves, the players will get to a leaf, marked by a x_{i} or by a \overline{x}_{i}, and they will agree upon the index i.

Second Direction: We prove the following claim: If A ∩ B = ϕ and C(A, B) = d then there exists a function f, for which the following holds: f(A) = 0, f(B) = 1 and D(f) ≤ d. This claim is easily seen to imply the result. Proof: We prove the claim by induction on d.

basis: For d = 0 the index is known in advance, so there exists an index i, such that for every x ∈ A and for every y ∈ B x_{i} ≠ y_{i}. We can let f be x_{i} if x_{i}’s value for A is 0, or let

f = \overline{x}_{i} if the value is 1.

step: Suppose the claim holds for d − 1. Let us examine a protocol that solves the communication problem (A, B) with complexity ≤ d. Assume that the first player of the protocol is I. Let A_{0} and A_{1} be the subdivision of A to the set of inputs on which I sends 0 and 1 respectively. For each of the communication problems (A_{0}, B) and (A_{1}, B), there is a protocol which uses at most d − 1 bits. Using the induction hypotheses, there are functions f_{0} and f_{1} such that: D(f_{0}), D(f_{1}) ≤ d − 1 and f_{0}(A_{0}) = f_{1}(A_{1}) = 0, f_{0}(B) = f_{1}(B) = 1. Define f = f_{0} ∧ f_{1}. f satisfies: D(f) ≤ d and f(A) = 0, f(B) = 1.

If the first player is II, using a similar argument we get f_{0} and f_{1} which return 1 on a subdivision B_{0}, B_{1} of B. In this case we take f to be f_{0} ∨ f_{1}.

Example (Example 1 Continued)

As we have seen in a previous lecture (this followed from Khrapchenco’s theorem), L_{U_{2}}(XOR_{n}) ≥ n^{2}, so D_{U_{2}}(XOR_{n}) ≥ 2 log n. By theorem 9.6, this means that the protocol in Example 1 above is optimal.

Conclusions:

1. For every f ∈ B_{n}, D_{U_{2}}(f) ≤ n + log^{∗} n. Actually it is known that D_{U_{2}}(f) ≤ n − log log n + O(1) for every f ∈ B_{n} (Gaskov ’78). This yields the bound: C(A, B) ≤ n − log log n for any A, B ⊂ \{0, 1\}^{n}, A ∩ B = ϕ. Since L_{U_{2}}(f) ≥ \frac{2^{n}}{log n} for most of the Boolean functions with n inputs, D_{U_{2}}(f) ≥ n − log log n for most of the Boolean functions, so we have a tight bound on the communication complexity C(A, B), for most A, B for which A ∪ B = {0, 1}^{n}, A ∩ B = ϕ.

2. D_{U_{2}}(MOD_{3}(n)) ≤ 2.89 log_{2} n by Exercise 2.

9.2.1 Monotone Depth and Communication Complexity

In this section we present a variant of the communication problem, whose complexity is related to the depth of monotone formulae. Note that in Theorem 9.6, if f is monotone, and if f(x) = 0 and f(y) = 1, then there exists an index i such that x_{i} < y_{i}. Moreover, a protocol corresponding to a monotone formula for f always finds such an i. Also, in the opposite direction, if we build a formula out of a protocol which always finds an index i such that x_{i} < y_{i}, then we will get a monotone formula (since no variable will be negated).

We can treat a vector x ∈ {0, 1}^{n} as a subset, {i | x_{i} = 1} of [n] = {1, 2, … n}. This defines a new communication problem: Let A, B ⊆ 2^{[n]}. Suppose that for all x ∈ A, y ∈ B we have x ∩ y ≠ ϕ. I gets a set x ∈ A.

II gets a set y ∈ B. They have to find a i ∈ x ∩ y. Let C_{M}(A, B) be the communication complexity of this problem.

Definition For a monotone function f we define:

max(f): The collection of all minimal sets of variables, such that substituting 1 in each, will make f return 1.

min(f): The collection of all minimal sets of variables, such that substituting 0 in each, will make f return 0.

Remark: Note that if x ∈ min(f) and y ∈ max(f) then x ∩ y ≠ ϕ, since otherwise f would have to return two values for a substitution in which 1 is substituted to the variables in x, and 0 to the variables in y.

Theorem 9.7 For every monotone function f:

D_{M}(f) = C_{M}(min(f), max(f)).

Proof: Let A = {x ⊆ [n] | x is a complement of a set on which f returns 0} and B = {y ⊆ [n] | f returns 1 on y}. First Direction: C_{M}(min(f), max(f)) ≤ D_{M}(f) First note that C_{M}(A, B) is a nondecreasing function of A and of B, since a protocol for the larger sets can be used for the smaller sets. min(f) ⊆ A and max(f) ⊆ B. By the argument above, C_{M}(A, B) ≤ D_{M}(f), so

C_{M}(min(f), max(f)) ≤ C_{M}(A, B) ≤ D_{M}(f).

Second Direction: We show that given a protocol for the problem (min(f), max(f)), we can get a protocol with the same complexity for (A, B). Given x ∈ A, I can find x′ ⊆ x such that x′ ∈ min(f) (x′ is a minterm). Given y ∈ B, II can find y′ ⊆ y such that y′ ∈ max(f) (y′ is a maxterm). I and II will perform the given protocol on x′, y′, which produces a i such that i ∈ x′ ∩ y′. This i also satisfies i ∈ x ∩ y, as required. By the above argument, this protocol can be turned into a monotone formula.