?
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.