ECCC-Report TR13-178https://eccc.weizmann.ac.il/report/2013/178Comments and Revisions published for TR13-178en-usMon, 30 Dec 2013 14:02:07 +0200
Revision 2
| Randomized communication complexity of appropximating Kolmogorov complexity |
Nikolay Vereshchagin
https://eccc.weizmann.ac.il/report/2013/178#revision2The paper [Harry Buhrman, Michal Koucky, Nikolay Vereshchagin. Randomized Individual Communication Complexity. 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 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 $\epsilon$, we show the lower bound $0.99n$ for (worst case) communication length of any randomized protocol that for all input pairs with probability at least 0.01 approximates $C(x|y)$ with precision $\epsilon n$Mon, 30 Dec 2013 14:02:07 +0200https://eccc.weizmann.ac.il/report/2013/178#revision2
Revision 1
| Randomized communication complexity of appropximating Kolmogorov complexity |
Nikolay Vereshchagin,
Harry Buhrman,
Michal Koucky
https://eccc.weizmann.ac.il/report/2013/178#revision1The paper [Harry Buhrman, Michal Koucky, Nikolay Vereshchagin. Randomized Individual Communication Complexity. 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 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 $\epsilon$, we show the lower bound $0.99n$ for (worst case) communication length of any randomized protocol that for all input pairs with probability at least 0.01 approximates $C(x|y)$ with precision $\epsilon n/\log n$Wed, 25 Dec 2013 10:18:20 +0200https://eccc.weizmann.ac.il/report/2013/178#revision1
Paper TR13-178
| Randomized communication complexity of appropximating Kolmogorov complexity |
Nikolay Vereshchagin
https://eccc.weizmann.ac.il/report/2013/178The paper [Harry Buhrman, Michal Koucky, Nikolay Vereshchagin. Randomized Individual Communication Complexity. 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 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 $\epsilon$, we show the lower bound $0.99n$ for (worst case) communication length of any randomized protocol that for all input pairs with probability at least 0.01 approximates $C(x|y)$ with precision $\epsilon n/\log n$Sat, 14 Dec 2013 14:29:53 +0200https://eccc.weizmann.ac.il/report/2013/178