Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR13-178 | 30th December 2013 14:02

Randomized communication complexity of appropximating Kolmogorov complexity

RSS-Feed




Revision #2
Authors: Nikolay Vereshchagin
Accepted on: 30th December 2013 14:02
Downloads: 1444
Keywords: 


Abstract:

The 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$



Changes to previous version:

In the first revision by a mistake the set of authors was incorrect,


Revision #1 to TR13-178 | 25th December 2013 10:18

Randomized communication complexity of appropximating Kolmogorov complexity





Revision #1
Authors: Harry Buhrman, Michal Koucky, Nikolay Vereshchagin
Accepted on: 25th December 2013 10:18
Downloads: 1056
Keywords: 


Abstract:

The 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$



Changes to previous version:

The lower bound is improved.


Paper:

TR13-178 | 14th December 2013 10:25

Randomized communication complexity of appropximating Kolmogorov complexity





TR13-178
Authors: Nikolay Vereshchagin
Publication: 14th December 2013 14:29
Downloads: 1569
Keywords: 


Abstract:

The 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$



ISSN 1433-8092 | Imprint