Résumé
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) \geq I(x:y \mid t(x,y)) - O(\log 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) \geq I(x:y \mid t(x,y)) - \log \rho - O(\log n)$ , where$t(x,y)$is any rectangle containing$(x,y)$and$\rho$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.