[24] Assume that a function f : {0, 1}n × {0, 1}n → {0, 1}

satisfies C(f|n) ≥ 22n − n: the truth table describing the outcomes of f for the 2n possible inputs x (the rows) and the 2n possible inputs for y

(the columns) has high Kolmogorov complexity. If we flip the truth table for a prospective f using a fair coin, then with probability at least 1−2−n it will satisfy this. Show that every deterministic protocol P computing such a function f requires at least CC(x, y|P) ≥ min{C(x|P), C(y|P)}−

log n − O(1).

Comments. Source: [H.M. Buhrman, H. Klauck, N.K. Vereshchagin, and P.M.B. Vit´anyi, J. Comput. Syst. Sci. 73(2007), 973–985].