On a conditional inequality in Kolmogorov complexity and its applications in communication complexity
share
Romashchenko and Zimand rom-zim:c:mutualinfo have shown that if we partition the set of pairs (x,y) of n-bit strings into combinatorial rectangles, then I(x:y) ≥ I(x:y | t(x,y)) - O( n), where I denotes mutual information in the Kolmogorov complexity sense, and t(x,y) is the rectangle containing (x,y). We observe that this inequality can be extended to coverings with rectangles which may overlap. The new inequality essentially states that in case of a covering with combinatorial rectangles, I(x:y) ≥ I(x:y | t(x,y)) - ρ - O( n), where t(x,y) is any rectangle containing (x,y) and ρ is the thickness of the covering, which is the maximum number of rectangles that overlap. We discuss applications to communication complexity of protocols that are nondeterministic, or randomized, or Arthur-Merlin, and also to the information complexity of interactive protocols.
READ FULL TEXT