We say that a protocol computes the function if on all possible input instances,at the end of the protocol,the party who receives the last message knows the function value on the input.(Sometimes for two-way communication model we assume that both parties know the function value.This doesn't change the complexity much since for Boolean functions,one party can always send the answer to the other party by just one bit.)For randomized protocols,we sometimes allow a small error probability. The cost of a protocol is measured by the number of communication bits.The commmication complexity ofa function f is the minimum cost of any protocol that computes the function.We ignore the issue of local computation cost by assuming that all parties are computationally all-powerful.Though all the computation factors are gone and only commmication is focused on,it turns out to be very helpful for communication complexity to be exploited to prove impossibility results for other computational complexity. 1.2 An efficient deterministic protocol Let's consider the basic case oftwo parties.Note that ifx and y are both at most n-bit long,then at the very least Alice can send her input to Bob,who then can compute f(x,y)since he has both inputs.Finally he tells Alice the answer by I bit communication.Thus the communication complexity of any 2n-bit function is at most n+1. What makes communication complexity interesting on its own is that some functions enjoy much more efficient protocols Example 1.Max.Alice and Bob hold,y E [0,1)n,respectively.Interpret x as a subset of [n] {1,2,...,n};the subset contains the positions i s.t.xi=1.Similarly for y.The task is to compute max(x,y),the maximum number in x Uy. If Alice sends her entire input x,it takes n communication bits.But she can do something better: She merely needs to send the maximal number in her set x,which only takes logn bits.Bob then compares this value with his maximal number in y.Thus the protocol only takes logn bits of communication.(If we want both parties to know the answer,then Bob can send the answer back to Alice which takes extra logn bits of communication.)This is much more efficient than sending n bits This protocol seems trivial,but some others need more thoughts. Example 2.Median.Alice and Bob again hold subsets x,y E(0,1)m,respectively.But this time they wish to compute the median of the multi-set x U y.Recall that the median of k numbers is defined as the [k/2]-th smallest number.We say that a protocol computes the function if on all possible input instances, at the end of the protocol, the party who receives the last message knows the function value on the input. (Sometimes for two-way communication model we assume that both parties know the function value. This doesn’t change the complexity much since for Boolean functions, one party can always send the answer to the other party by just one bit.) For randomized protocols, we sometimes allow a small error probability. The cost of a protocol is measured by the number of communication bits. The communication complexity of a function 𝑓 is the minimum cost of any protocol that computes the function. We ignore the issue of local computation cost by assuming that all parties are computationally all-powerful. Though all the computation factors are gone and only communication is focused on, it turns out to be very helpful for communication complexity to be exploited to prove impossibility results for other computational complexity. 1.2 An efficient deterministic protocol Let’s consider the basic case of two parties. Note that if 𝑥 and 𝑦 are both at most 𝑛-bit long, then at the very least Alice can send her input to Bob, who then can compute 𝑓(𝑥, 𝑦) since he has both inputs. Finally he tells Alice the answer by 1 bit communication. Thus the communication complexity of any 2𝑛-bit function is at most 𝑛 + 1. What makes communication complexity interesting on its own is that some functions enjoy much more efficient protocols. Example 1. Max. Alice and Bob hold , 𝑦 ∈ {0,1} 𝑛 , respectively. Interpret 𝑥 as a subset of [𝑛] = {1,2, …, 𝑛}; the subset contains the positions 𝑖 s.t. 𝑥𝑖 = 1. Similarly for 𝑦. The task is to compute max(𝑥,𝑦), the maximum number in 𝑥 ∪ 𝑦. If Alice sends her entire input 𝑥, it takes 𝑛 communication bits. But she can do something better: She merely needs to send the maximal number in her set 𝑥, which only takes log 𝑛 bits. Bob then compares this value with his maximal number in 𝑦. Thus the protocol only takes log 𝑛 bits of communication. (If we want both parties to know the answer, then Bob can send the answer back to Alice which takes extra log 𝑛 bits of communication.)This is much more efficient than sending 𝑛 bits. This protocol seems trivial, but some others need more thoughts. Example 2. Median. Alice and Bob again hold subsets 𝑥,𝑦 ∈ {0,1} 𝑛 , respectively. But this time they wish to compute the median of the multi-set 𝑥 ∪ 𝑦. Recall that the median of 𝑘 numbers is defined as the ⌊𝑘/2⌋-th smallest number