On a conditional inequality in Kolmogorov complexity and its applications in communication complexity

Andrei Romashchenko, Marius Zimand

Romashchenko and Zimand~\cite{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…