Example 1.2.Median.Alice and Bob again hold subsets x,ye(0,1),respectively.Now they wish to compute the median of the multi-set x Uy.Recall that the median ofk numbers is defined as the Lk/2th smallest number. An efficient protocol is as follows.At any point,they maintain an interval [l,u]which guarantees to contain the median.Initially I=I and u=n.They halve the interval in each round,so it takes only log(n)rounds to finish.How do they halve the interval?Actually very simple:Alice sends to Bob the number ofher elements that are at least m=(1+u)/2,and the number ofelements that are less than m. This information is enough for Bob to know whether the median is above m or not.(Verify this!)Bob uses I bit to indicate the answer,and then the protocol goes to the next round. Since each round hasonly O(log(n))bits,and there are only log(n)rounds,the total communication cost is O(log2(n)),much more efficient than the trivial protocol of cost n+1. 1.3 Hardness for deterministic and rescue by randomness We've seen examples ofefficient protocols.On the other hand,for some problems,there isn't any protocol using communication less than n bits. First,let's observe that a deterministic communication protocol partitions the communication matrix into monochromatic rectangles.Here for a function f(x,y),the communication matrix M is defined by [f(x,y)l),namely the rows are indexed by x and the columns are indexed by y,and the(x,y)-entry is f(x,y).A rectangle is a pair of subsets(S,T)where S is a set of rowsand T is a set of columns.A rectangle (S,T)is monochromatic if Me restricted on it is a submatrix containing only one value. (Namely,all entries in the submatrix are of the same value.)For any value b in range(f),a b-rectangle is a monochromatic rectangle in which all entries of Mr are of value b.By considering how the protocol goes round-by-round,we can observe the following fact. Fact 1.1.A c-bit deterministic communication protocol for fpartitions the communication matrix M into 2 monochromatic rectangles. Example 1.3.Equality. The above fact enables us to show that there is no efficient protocol for solving the Equality function EQ.Indeed,the communication matrix for EQ is IN,the identity matrix of size N=2.Notice that for this matrix,all 1-rectangles are of size 1x1.So no matter how one partitions the matrix intoExample 1.2. Median. Alice and Bob again hold subsets x,y{0,1}n , respectively. Now they wish to compute the median of the multi-set x∪y. Recall that the median of k numbers is defined as the k/2 th smallest number. An efficient protocol is as follows. At any point, they maintain an interval [l,u] which guarantees to contain the median. Initially l = 1 and u = n. They halve the interval in each round, so it takes only log(n) rounds to finish. How do they halve the interval? Actually very simple: Alice sends to Bob the number of her elements that are at least m = (l+u)/2, and the number of elements that are less than m. This information is enough for Bob to know whether the median is above m or not. (Verify this!) Bob uses 1 bit to indicate the answer, and then the protocol goes to the next round. Since each round has only O(log(n)) bits, and there are only log(n) rounds, the total communication cost is O(log2 (n)), much more efficient than the trivial protocol of cost n+1. 1.3 Hardness for deterministic and rescue by randomness We've seen examples of efficient protocols. On the other hand, for some problems, there isn't any protocol using communication less than n bits. First, let’s observe that a deterministic communication protocol partitions the communication matrix into monochromatic rectangles. Here for a function f(x,y), the communication matrix Mf is defined by [f(x,y)](x,y), namely the rows are indexed by x and the columns are indexed by y, and the (x,y)-entry is f(x,y). A rectangle is a pair of subsets (S,T) where S is a set of rows and T is a set of columns. A rectangle (S,T) is monochromatic if Mf restricted on it is a submatrix containing only one value. (Namely, all entries in the submatrix are of the same value.) For any value b in range(f), a b-rectangle is a monochromatic rectangle in which all entries of Mf are of value b. By considering how the protocol goes round-by-round, we can observe the following fact. Fact 1.1. A c-bit deterministic communication protocol for f partitions the communication matrix Mf into 2 c monochromatic rectangles. Example 1.3. Equality. The above fact enables us to show that there is no efficient protocol for solving the Equality function EQn. Indeed, the communication matrix for EQn is IN, the identity matrix of size N=2n . Notice that for this matrix, all 1-rectangles are of size 11. So no matter how one partitions the matrix into