Lecture 1.Samples of possibility and impossibility results in algorithm designing The course is about the ultimate efficiency that algorithms and communication protocols can achieve in various settings.In the first lecture,we'll see a couple ofcleverly designed algorithms/protocols, and also prove several impossibility results to show limits ofalgorithms in various computation settings 1.Communication complexity. 1.1 Setup In information theory,we are usually concerned with transmitting a message through a noisy channel In communication complexity,we consider the problem of computing a function with input variables distributed to two(or more)parties.Since each party only holds part of the input,they need to communicate in order to compute the function value.The communication complexity measures the minimum communication needed. The most common communication models include two-way:two parties,Alice and Bob,holding inputs x and y,respectively,talk to each other back and forth. one-way:two parties,Alice and Bob,holding inputs x andy,respectively,but only Alice sends a message to Bob. Simultaneous Message Passing (SMP):Three parties:Alice,Bob and Referee.Alice and Bob hold inputs x and y,respectively,and they each send one message to Referee,who then outputs an answer. multiparty:k parties,each holding some input variables and they communicate in a certain way. Some example functions are: Equality (EQ):To decide whether x=y,where x.ye(0,1)" Inner Product (IP):To compute (x,y)=xiy1+...+xnyn mod 2,where x.ye(0,1)n Disjointness (Disj):To decide whether 3is.t.x;=y;=1 for x,ye(0,1)". The computation modes includeLecture 1. Samples of possibility and impossibility results in algorithm designing The course is about the ultimate efficiency that algorithms and communication protocols can achieve in various settings. In the first lecture, we’ll see a couple of cleverly designed algorithms/protocols, and also prove several impossibility results to show limits of algorithms in various computation settings. 1. Communication complexity. 1.1 Setup In information theory, we are usually concerned with transmitting a message through a noisy channel. In communication complexity, we consider the problem of computing a function with input variables distributed to two (or more) parties. Since each party only holds part of the input, they need to communicate in order to compute the function value. The communication complexity measures the minimum communication needed. The most common communication models include  two-way: two parties, Alice and Bob, holding inputs x and y, respectively, talk to each other back and forth.  one-way: two parties, Alice and Bob, holding inputs x and y, respectively, but only Alice sends a message to Bob.  Simultaneous Message Passing (SMP): Three parties: Alice, Bob and Referee. Alice and Bob hold inputs x and y, respectively, and they each send one message to Referee, who then outputs an answer.  multiparty: k parties, each holding some input variables and they communicate in a certain way. Some example functions are:  Equality (EQn): To decide whether x = y, where x,y{0,1}n .  Inner Product (IPn): To compute x,y= x1y1 + … + xnyn mod 2, where x,y{0,1}n .  Disjointness (Disjn): To decide whether i s.t. xi = yi = 1 for x,y{0,1}n . The computation modes include