An efficient protocol is as follows.At any point,they maintain an interval [l,u]which guaranteesto contain the median.Initially l=1 and u =n.They halve the interval in each round,so it takes only logn 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=(l+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(logn)bits,and there are only logn rounds,the total communication cost is 0(log2n),much more efficient than the trivial protocol ofcost n +1. 1.3 Hardness for deterministic and saving by randomness We've seen examples of efficient protocols.On the other hand,for some problems,there isn't any protocol with 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 Mr is defined by [f(x,y)x 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 Mr 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 whichall entries of Mr are of value b.By considering how the protocol goes round-by-round,we can observe the following fact. Fact 1.A c-bit deterministic communication protocol for f partitions the communication matrix Mp into 2c monochromatic rectangles. Example 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 I-rectangles are of size Ix1.So no matter how one partitions the matrix into monochromatic rectangles,there are always N 1-rectangles.Considering that there are also 0-rectangles,we have 2c>N =2n,so c>n.We have thus proved the following theorem Theorem 2.Any deterministic protocol computing EQn needs n+1 bits of communication.An efficient protocol is as follows. At any point, they maintain an interval [𝑙,𝑢] which guarantees to contain the median. Initially 𝑙 = 1 and 𝑢 = 𝑛. They halve the interval in each round, so it takes only log𝑛 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 𝑚 = (𝑙 + 𝑢)/2, and the number of elements that are less than 𝑚. This information is enough for Bob to know whether the median is above 𝑚 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𝑛) bits, and there are only log𝑛 rounds, the total communication cost is O(log2 𝑛), much more efficient than the trivial protocol of cost 𝑛 + 1. 1.3 Hardness for deterministic and saving by randomness We've seen examples of efficient protocols. On the other hand, for some problems, there isn't any protocol with communication less than 𝑛 bits. First, let’s observe that a deterministic communication protocol partitions the communication matrix into monochromatic rectangles. Here for a function 𝑓(𝑥, 𝑦), the communication matrix 𝑀𝑓 is defined by [𝑓(𝑥,𝑦)]𝑥,𝑦, namely the rows are indexed by 𝑥 and the columns are indexed by 𝑦, and the (𝑥,𝑦)-entry is 𝑓(𝑥, 𝑦). A rectangle is a pair of subsets (𝑆,𝑇) where 𝑆 is a set of rows and 𝑇 is a set of columns. A rectangle (𝑆,𝑇) is monochromatic if 𝑀𝑓 restricted on it is a submatrix containing only one value. (Namely, all entries in the submatrix are of the same value.) For any value 𝑏 in 𝑟𝑎𝑛𝑔𝑒(𝑓), a 𝑏-rectangle is a monochromatic rectangle in which all entries of 𝑀𝑓 are of value 𝑏. By considering how the protocol goes round-by-round, we can observe the following fact. Fact 1. A 𝑐-bit deterministic communication protocol for 𝑓 partitions the communication matrix 𝑀𝑓 into 2 𝑐 monochromatic rectangles. Example 3. Equality. The above fact enables us to show that there is no efficient protocol for solving the Equality function 𝐄𝐐𝑛. Indeed, the communication matrix for 𝐄𝐐𝑛 is 𝐼𝑁, the identity matrix of size 𝑁 = 2 𝑛. Notice that for this matrix, all 1-rectangles are of size 11. So no matter how one partitions the matrix into monochromatic rectangles, there are always 𝑁 1-rectangles. Considering that there are also 0-rectangles, we have 2 𝑐 > 𝑁 = 2 𝑛, so 𝑐 > 𝑛. We have thus proved the following theorem. Theorem 2. Any deterministic protocol computing 𝐄𝐐𝑛 needs 𝑛 + 1 bits of communication