[37] We continue Exercise  6.11.3.

Let hx(i) be the structure function as in Definition 5.5.6 on page 413. Define, with P a protocol that computes the identity function I, the protocol-size function py(j) = min{i : TCC(x, y|C(P) ≤ i, P is one-way ) ≤ j}. The function py(j) gives the minimal number of bits of a protocol of the total deterministic type considered that transmits y ∈ {0, 1}∗ in at most j bits of communication. By Exercise 6.11.3, Item (c), total one-way protocols are as powerful as total two-way protocols of about the same complexity.

Note that the one-way protocol does not depend on x.

(a) Show that py(j) = hy(j) + O(log n) for all y and j.

(b) Use item

(a) to show the following: (i) For every string y of length n we have py(n) = O(1) and 0 ≤ py(j) − py(k) ≤ k − j + O(log n), for every j

replaced by 0, then there is a string y of length n such that py(j) =

p(j) + O(log n + C(p)), where C(p) stands for the complexity of the set

{(j, p(j)) : j ∈ {0,...,n}}.

(c) Show that there exist noncommunicable strings in the following sense.

Let k

(b) to the function p defined as p(j) = k for j ≤ n−k and p(j) = n−j for j ≥ n−k. By Item

(b) there exists a string y of length n such that py(0) = k + O(log n) (thus C(y) = k + O(log n))

and the protocol-independent communication complexity for the identity function I is TCC(x, y|C(P) ≤ i, P is one-way) > n − i − O(log n) for every i

Comments. Item

(c) shows that Bob can hold a highly compressible string y, but cannot use that fact to reduce the communication complexity significantly below l(y). Unless all information about y is hardwired into the protocol, the communication between Bob and Alice requires sending y almost completely literally. Indeed, For such y with, say, C(y) = logO(1) n, we have (irrespective of x) communication complexity that is exponential in the complexity of y for all protocols of complexity less than that of y. When the complexity of the protocol reaches the complexity of y, the communication complexity suddenly drops to 0. Source: [H.M. Buhrman, H. Klauck, N.K. Vereshchagin, and P.M.B.
Vit´anyi, Ibid.].