### ?

## Randomized communication complexity of approximating Kolmogorov complexity

The paper [Harry Buhrman, Michal Kouck ́, Nikolay Vereshcha-

y

gin. Randomized Individual Communication Complexity. IEEE Con-

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.