Boolean Circuit Complexity Fall Semester, 1994-5

Lecture 10: December 29th

Lecturer: Uri Zwick Scribe: Guy Mayraz

10.1 Communication Complexity

Let us consider the following scenario: A and B would like to calculate a function f(x, y) of two sets of variables, where x and y are two n-bit vectors. A and B both have an unlimitied computing power, but x is known only to A, and y only to B. A and B can exchange messages, and our concern is with the size of these messages.

Formally, given a function f(x, y) of two n-bit vectors, we can define a square matrix C of size 2^{n} × 2^{n}, so that C_{x,y} = f(x, y). We assume that A holds the index x of a row in C, and that B holds the index y of a column in C. A and B must find C_{x,y}. We can now make the following definition:

Definition: The communication complexity of the matrix C is the minimal number of bits A and B must exchange in the worst case of a protocol, in the end of which both A and B know the value of f. We will denote the communication complexity of C by K(C).

The following is a trivial upper bound:

Theorem 10.1 For C ∈ M_{2^{n}×2^{n}} we have K(C) ≤ n + 1.

Proof: A sends x (n bits) to B. B calculates C_{x,y} and sends the result bit back to A.

Denoting the rank of C by rk(C), we have the following lower bound:

Theorem 10.2 If rk(C) ≥ 1 then K(C) ≥ 1 + log rk(C).

Proof: The first bit sent over the communication line defines a division of C into two parts (two rectangular blocks if we allow permutations on the rows and columns). The next bits split the matrix further. A protocol for C defines a tree of divisons of C. The protocol halts when we arrive at a constant sub-matrix (all 0’s or all 1’s). If during the protocol at most t bits are sent, then our tree has at most 2^{t} leaves, each of which is a constant sub-matrix, and its parent node is not constant. An immediate conclusion is that the 1’s in C can be described as a union of no more than 2^{t−1} sub-matrices, that are all 1’s. Denote by M_{i} the matrix we get by expanding the i’th 1’s sub-matrix by assigning 0’s to all the locations outside the sub-matrix. Using these definitions we have C = ∑_{i=1}^{2^{t−1}} M_{i} and also rk(M_{i}) ≤ 1. Therefore rk(C) ≤ 2^{t−1} and therefore t ≥ 1 + log rk(C).

Proof: (alternative) Every bit over the communication line divides C into two submatrices: C_{1} and C_{2}. Now, rk(C) ≤ rk(C_{1}) + rk(C_{2}) ⟹ ∃i | rk(C_{i}) ≥ \frac{rk(C)}{2}. From this we get K(C) ≥ 1 + K(C_{i}). By induction we get the theorem.

10.1.1 Examples

• Example 1: f(x, y) = 1 ⟺ x = y.

Here C is the identity matrix and its rank is 2^{n} so we have K(C) = n + 1.

• Example 2: f(x, y) = 1 ⟺ x_{i} = 0 ∨ y_{i} = 0. (the sets represented by x and y are disjoint). Here too C is of rank 2^{n} so we have K(C) = n + 1.

Proof: We will use an induction on n. The case of n = 1 is trivial. Considering the general case we note that the matrix of the communication problem, C_{n}, can be divided into four quarters according to the most significant bit where the bottom right quarter is zeroes, and the other quarters are copies of C_{n−1}. We have to prove that only a trivial combination of the lines produces a zero vector. Suppose there is a non trivial linear combination of the lines that sums into a zero vector. If the combination includes vectors from the upper half of the matrix, we get a non zero right half of the sum vector. Therefore, we can assume we have non zero coefficents only in the lower half of the matrix. But then, considering only the left half of each line, the problem reduces into the case of C_{n−1} for which we assume we already have a proof.

10.1.2 Probabilistic Protocols

Now we allow A and B to flip coins. The protocol may fail with a probability ϵ < \frac{1}{2}.

• Example: C is the identity matrix Id_{n}.

A randomly picks a prime number 2 < p < n^{2}, and sends p and x mod p to B. This takes O(log n) bits. B decides “yes” iff x = y(modp) and sends his decision to A. This is the end of the protocol. If x = y the result of the protocol is always correct. If x ≠ y the protocol can err. The protocol errs when A picks a prime p, such that p divides |x−y|. Now, |x−y| < 2^{n}, and therefore the number of primes dividing |x − y| is no more than log 2^{n} = n. We are choosing a prime with equal probability from a collection of size n^{2}/ log n^{2}. Therefore, we get the following estimate:

P r\{error\} ≤ \frac{n}{n^{2}/ log^{2} n} = \frac{2 log n}{n} < \frac{1}{3}

10.2. USING COMMUNICATION COMPLEXITY TO OBTAIN LOWER BOUNDS ON MONOTONEUS DEPTH OF BOOLEAN FUNCTIONS3

The deterministic complexity of the identity is C(Id_{n}) = n + 1, but the probabilistic complexity is only C_{\frac{1}{3}} (Id_{n}) = O(log(n)). On the other hand, we have C(Distjointness_{n}) = n + 1 and the probabilistic complexity in this case is Ω(n). This lower bound was proved by Kalyanasundaram and Schnitger. A considerably simpler proof was found by Razborov.

10.2 Using communication complexity to obtain lower bounds on monotoneus depth of Boolean functions

In the previous lecture we have established a connection between monotoneus depth and communication complexity: The monotoneus depth of a monotoneus function f is the same as the complexity of the following communication problem: A receives a minterm x of f, and B receives a maxterm y of f. Their problem is to find an index i satisfying i ∈ x ∩ y. (A minterm is a minimal set of variables, such that setting the value of all the variables in the set to 1 forces the value of f to 1. A maxterm is a minimal set of variables, such that setting the value of all the variables in the set to 0 forces the value of f to 0. Obviously maxterms and minterms are always intersecting for otherwise it were possible to force f to two different values).

Let us define the following problem: Definition: Match_{n} is a function f of \binom{n}{2} variables, so that f is 1 if and only if the graph defined by these variables contains a matching of size m = \frac{n}{3}.

Theorem 10.3 Raz and Wigderson D_{m}(Match_{n}) = Ω(n).

Proof: Consider the following subcase (denote it by M_{n}) of the communication problem corresponding to the function Match_{n}: A receives a matching P of size m. B receives a set of vertices Q of size m − 1 (corresponding to a clique on the other vertices). We note that the edges in the clique on 2m + 1 vertices is a maxterm of Match_{n}. A and B must find an edge e so that e ∈ P \ Q.

Using a series of reductions we will show that

D_{m}(Match_{n}) ≤ C(M_{n}) ≤ C_{\frac{1}{3}} (DISJ_{n}) = Ω(n)

(The novel part is the second inequality).

Denote by {e_{1}, …, e_{i}} the edges in P which do not intersect Q. Denote by j the number of edges in P that have both vertices in Q. Let T be an optimal deterministic protocol for M_{n}. T returns an edge in {e_{1}, …, e_{i}}. We transform T into a probabilistic protocol T′ as follows: A and B will jointly pick a random permutation π on the vertices {1, …, n} of the graph, and then execute T on π_{P} and π_{Q}. It is evident that T′ will return each edge of {e_{1}, …, e_{i}} with equal probabilities.

Let us now consider the following decision problem M̂: A receives a matching P of size m. B receives a set Q̂ of vertices of size m. A and B will have to decide whether there exists an edge e ∈ P \ Q̂. We transform the protocol T′ into another (probabilistic) protocol T̂ for the problem M̂ as follows: B randomly chooses a vertex u ∈ Q̂ (with uniform distribution). Define Q = Q̂ \ {u}. A and B execute T′ on P and Q and so find an edge e ∈ P \ Q. B will check whether u ∈ e and send the result to A. The answer will be ‘no’ iff u ∈ e.

If there is no edge e ∈ P \ Q̂, the result of the protocol is always correct. Let us find the probability of T̂ returning ‘no’ in the case that there is an edge e ∈ P \Q̂. For this to happen we must have that there is more than one edge in P \ Q̂. If the vertex u is not incedent to any edge in the matching, or u is contained in an edge that has both vertices in Q̂ then the answer of the protocol is correct. We will have a wrong anwer iff we have chosen a vertex incedent to an edge with exactly one vertex in Q̂. In this case, the protocol is as likely to choose this edge as the edges that are in P and have no vertices in Q. We will, therefore, choose it with probability P r\{error\} = \frac{1}{i+1}. But since i ≥ 1 we have P r\{error\} ≤ \frac{1}{2}. To reduce the probability of error we can repeat this algorithm once more.

So far we have proved: If there is no edge e ∈ P \ Q̂ then T̂ returns 0 always. If there is an edge e ∈ P \ Q̂ then T̂ returns 1 with a probability ≥ \frac{1}{2}.

Define the following protocol Ť: With probability \frac{1}{3} return 1. With probability \frac{2}{3} execute T̂. If there is no edge e ∈ P \ Q̂ then Ť returns 0 with probability \frac{2}{3}. If there is an edge e ∈ P \ Q̂ then Ť returns 1 with a probability ≥ \frac{1}{3} + \frac{2}{3} · \frac{1}{2} = \frac{2}{3}.

We have

C(Ť) = C(T) + 1

.

Therefore, we get

C(M) ≥ C_{\frac{1}{3}} (M̂) − 1

Consider the distinctness problem: A receives a vector x ∈ {0, 1, 2}^{n}. B receives a vector y ∈ {0, 1, 2}^{n}. A and B must determine if ∀i : x_{i} ≠ y_{i}.

Claim 10.4 C_{\frac{1}{3}} (M̂) ≥ C_{\frac{1}{3}} (distinctness).

Proof: Consider a graph on 3n vertices divided into n triplets. Define a numbering on the vertices of each triplet. B defines a set of vertices Q̂ of size n as follows: for each Using communication complexity to obtain lower bounds on monotoneus depth of Boolean functions5

1 ≤ i ≤ n, Q̂ includes the y_{i}’th vertex in the i’th triplet. A and B will now execute an optimal probabilistic protocol for the problem M̂.

Claim 10.5 (Ran Raz and Avi Wigderson) C_{\frac{1}{3}} (distinctness_{n}) ≥ C_{\frac{1}{3}} (distjointness_{n}).

Proof: Given inputs x and y for distjointness we define trenary vectors x′ and y′ as follows: x′_{i} = x_{i}. y′_{i} = 2 − y_{i}. We have that x and y are distjoint ⟺ x′ and y′ are ‘distinct’ (as defined in the the distinctness problem). Now execute the protocol for distinctness.