Randomized communication complexity of appropximating Kolmogorov complexity

2013. No. TR13-178.

Vereshchagin N.

The paper [Harry Buhrman, Michal Kouck\'y, Nikolay Vereshchagin. Randomized Individual Communication Complexity. \emph{IEEE Conference on Computational Complexity} 2008: 321-331] considered communication 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 approximating  $C(x|y)$ with precision $\alpha$ is at least $n-2\alpha-O(1)$. The above referenced  paper asks what is \emph{randomized} communication complexity of this problem and shows that for $r$-round randomized protocols its communication complexity is at least $\Omega((n/\alpha)^{1/r})$. In this paper, for some positive $\eps$, we show  the lower bound  $0.99n$ for (worst case) communication length of any randomized protocol that with probability at least 0.01 approximates $C(x|y)$ with precision  $\eps n/\log n$ for all input pairs.

Keywords: communication complexity, Kolmogorov complexity