Abstract

ference on Computational Complexity 2008: 321-331] considered com-munication complexity of the following problem. Alice has a bi-nary string x and Bob a binary string y, both of length n, and they want to compute or approximate Kolmogorov complexity C(x|y) of x conditional to y. It is easy to show that deterministic communica-tion complexity of approximating C(x|y) with precision α is at least n − 2α − O(1). The above referenced paper asks what is random-ized communication complexity of this problem and shows that for r-round randomized protocols its communication complexity is at least Ω((n/α)1/r). In this paper, for some positive ε, we show the lower bound 0.99n for (worst case) communication length of any random-ized protocol that with probability at least 0.01 approximates C(x|y) with precision εn for all input pairs.