Communication Complexity (Yao 1979) f(a,b) #of bits communicated a b Han Meimei Li Lei EQ:{0,1}m×{0,1}m→{0,1} Theorem(Yao,1979) There is no deterministic communication protocol solving EQ with less than n bits in the worst-case.Communication Complexity (Yao 1979) Han Meimei Li Lei EQ : {0, 1}n × {0, 1}n → {0, 1} # of bits communicated a b f(a, b) EQ(a, b) = ! 1 a = b There is no deterministic communication protocol 0 a ̸= b solving EQ with less than n bits in the worst-case. Theorem (Yao, 1979)