[24] Let f be the equality function, with f(x, y) = 1 if x = y and 0 otherwise. Show that for every deterministic protocol P computing

f, we have CC(x, x|P) ≥ C(x|P)− O(1) for all x, y. On the other hand, there is a P of complexity O(1) such that there are x, y (x = y) with C(x|P), C(y|P) ≥ n − 1 for which CC(x, y|P) = 2.

Comments. Source: [H.M. Buhrman, H. Klauck, N.K. Vereshchagin, and P.M. B. Vit´anyi, Ibid.].