k,r)-y,r〉=x-y,r）=(&-y)r1+.+(xnyn)r mod2 =(X-yr:+∑i(-y)mod2 =r+∑j(X-y)加mod2. Now notice that ri takes value 0 and I each with half probability,so regardless of the value of the second item,the summation is I always with probability half.Thus with probability half the protocol detects that x≠y. To make the error probability smaller,one can simply repeat the above protocol k times,dropping the error probability to 1/2k 1.4 Using communication complexity to show computational hardness:a taste Apart from being a very natural and interesting subject on its own,communication complexity is also widely used to prove limitation results for numerous computational models,including data structures, circuit complexity,streaming algorithms,decision tree complexity,VLSI,algorithmic game theory, optimization,pseudo-randomness...Here we just give one such example,with more coming up later in the course. Example 1.4.Lower bound on time-space tradeoff on TM for explicit decision problems. First let's recall the concept of multi-tape Turing machine(TM).Below I just copied the short description in [KN97],which is pretty intuitive without losing much rigor.For detailed definition,you can see standard textbooks such as [Sip02],or the wiki links above.x,r - y,r = x-y,r = (x1-y1)r1 + … + (xn-yn)rn mod 2 = (xi-yi)ri + ∑j≠i (xj-yj)rj mod 2 = ri + ∑j≠i (xj-yj)rj mod 2. Now notice that ri takes value 0 and 1 each with half probability, so regardless of the value of the second item, the summation is 1 always with probability half. Thus with probability half the protocol detects that x ≠ y. To make the error probability smaller, one can simply repeat the above protocol k times, dropping the error probability to 1/2k . 1.4 Using communication complexity to show computational hardness: a taste Apart from being a very natural and interesting subject on its own, communication complexity is also widely used to prove limitation results for numerous computational models, including data structures, circuit complexity, streaming algorithms, decision tree complexity, VLSI, algorithmic game theory, optimization, pseudo-randomness… Here we just give one such example, with more coming up later in the course. Example 1.4. Lower bound on time-space tradeoff on TM for explicit decision problems. First let’s recall the concept of multi-tape Turing machine (TM). Below I just copied the short description in [KN97], which is pretty intuitive without losing much rigor. For detailed definition, you can see standard textbooks such as [Sip02], or the wiki links above