Аннотация:The paper [Harry Buhrman, Michal Kouck ́, Nikolay Vereshcha-
y
gin. Randomized Individual Communication Complexity. IEEE Confer-
ence on Computational Complexity 2008: 321-331] considered communi-
cation complexity of the following problem. Alice has a binary 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 communication complexity of approx-
imating C(x|y) with additive error α is at least n − 2α − O(1). The above
referenced paper asks what is randomized communication complexity of
this problem and shows that for r-round randomized protocols its com-
munication complexity is at least Ω((n/α)1/r ). In this paper, for some
positive ε, we show the lower bound 0.99n for (worst case) communi-
cation length of any randomized protocol that with probability at least
0.01 approximates C(x|y) with additive error εn for all input pairs.