I was reading a wikipedia article about communication complexity and it seems to me that it bears some resemblance to Kolmogorov complexity. Was the founder of communication complexity influenced by Kolmogorov complexity?
$\begingroup$
$\endgroup$
6
-
4$\begingroup$ Yao's paper does not cite Kolmogorov directly, but he cites Rabin's Probabilistic Algorithms from Algorithms and Complexity volume, which is dedicated to computational complexity. So yes, he was aware of it. But Kolmogorov aimed at "intrinsic" complexity, rather than information transfers a la Shannon that Yao uses, and the two measures are orthogonal to each other. $\endgroup$– ConifoldJul 7, 2020 at 19:08
-
$\begingroup$ How are they "Orthogonal to each other"? Is it only because Kolmogorov complexity is thought to measure the intrinsic complexity of things? $\endgroup$– GEPJul 7, 2020 at 20:04
-
2$\begingroup$ "Unlike in computational complexity theory, communication complexity is not concerned with the amount of computation performed by Alice or Bob, or the size of the memory used". $\endgroup$– ConifoldJul 7, 2020 at 20:05
-
$\begingroup$ But still they are both kind of concerned with the amount of information needed to describe an object, either via communication or through a program. Am I wrong? $\endgroup$– GEPJul 7, 2020 at 20:20
-
1$\begingroup$ Yes, any two things are related if you make it vague enough. $\endgroup$– ConifoldJul 7, 2020 at 20:23
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
As pointed out by Conifold in the comments, the answer of the history seems likely that Yao was surely aware of Kolmogorov complexity at the time, but that the introduction of communication complexity was more motivated by communication between agents or processors than any connection with Kolmogorov complexity.
That said, there are some relations between the two concepts, for example:
- Vereshchagin Randomized Communication Complexity of Approximating Kolmogorov Complexity (preprint of full version available here)
- Kaplan & Laplante, Kolmogorov complexity and combinatorial methods in communication complexity
- Mora, Briegel, & Kraus, Quantum Kolmogorov complexity and its applications
$\begingroup$
$\endgroup$
The first link says that
communication complexity studies the amount of communication required to solve a problem when the problem is distributed between two or more parties.
Whilst the second link says that
Kolmogorov complexity of an object, such as a piece of text, is the length of the shortest computer program... that produces the object as output. It is a measure of the computational resource...
Had you read further down in the first link you would have discovered:
Note that unlike computational complexity theory, communication complexity is not concerned with the amount of computation performed by Alice or Bob, or the size of the memory used, as we assume nothing about the computational power of Alice or Bob.
So, no, the two concepts are not at all related other than sharing the word 'complexity' in their names. And that connection is spurious.
