deterministic:all messages are deterministically specified in the protocol.Namely,each message of any party depends only on her input and the previous messages that she saw. randomized:parties can use randomness to decide the messages they send. quantum:the parties have quantum computers and they send quantum messages.(We will not study this mode,or in general,any quantum computing topic,in this course.) In the two-way and one-way model,we say that a protocol computes the function if on all possible input instances,at the end ofthe protocol,both parties know the function value on the input.(In the SMP model,the Referee is required to know the function value.)For randomized protocol,we sometimes allow a small error probability.The cost of a protocol is measured by the total communication bits.The communication complexity of a 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 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.(More on this later.) 1.2 An efficient deterministic protocol Let's consider the basic case of two 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 1 bit communication.Thus the communication complexity ofany 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.1.Max.Alice and Bob hold x,ye(0,1),respectively.Interpret x as a subset of [n]= (1,2,...,n);the subset contains the positions is.t.x:=1.Similarly fory.The task is to compute Max(x,y),the maximal number in x Uy.If Alice sends her entire input,it takes n communication bits. But she can clearly do something better:She merely needs to send the maximal number in her set x, which only takeslog(n)bits.Bob then compares this value with his maximal number in y,and sends the larger one back to Alice as the answer.Altogether the protocol needs only 2l0g(n)bits. This protocol seems trivial,but some others need more thoughts. deterministic: all messages are deterministically specified in the protocol. Namely, each message of any party depends only on her input and the previous messages that she saw.  randomized: parties can use randomness to decide the messages they send.  quantum: the parties have quantum computers and they send quantum messages. (We will not study this mode, or in general, any quantum computing topic, in this course.) In the two-way and one-way model, we say that a protocol computes the function if on all possible input instances, at the end of the protocol, both parties know the function value on the input. (In the SMP model, the Referee is required to know the function value.) For randomized protocol, we sometimes allow a small error probability. The cost of a protocol is measured by the total communication bits. The communication complexity of a 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 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. (More on this later.) 1.2 An efficient deterministic protocol Let’s consider the basic case of two parties. Note that if x 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 1 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.1. Max. Alice and Bob hold x,y{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 maximal number in x∪y. If Alice sends her entire input, it takes n communication bits. But she can clearly do something better: She merely needs to send the maximal number in her set x, which only takes log(n) bits. Bob then compares this value with his maximal number in y, and sends the larger one back to Alice as the answer. Altogether the protocol needs only 2log(n) bits. This protocol seems trivial, but some others need more thoughts