18th Annual IEEE Conference on Computational Complexity (CCC'03)
Extracting the Mutual Information for a Triple of Binary Strings
Aarhus, Denmark
July 07-July 10
ISBN: 0-7695-1879-6
We say that the mutual information of a triple of binary strings a; b; c can be extracted if there exists a string d such that a, b, and c are independent given d, and d is simple conditional to each of the strings a, b, c. This is an analog of the well-known Gács-Körner's definition of extrability of the mutual information for a pair of binary strings. We prove that (in contrast to the case of two strings) there exists a criterion of extrability of the mutual information for a triple a; b; c in terms of complexities involving a; b; c. Roughly speaking, the mutual information between a; b; c can be extracted if and only if the conditional mutual informations I(a : b/c),I(a : c/b), I(b : c/a) are negligible. Our proof of the main result is based on a non-Shannontype information inequality, which is a generalization of the recently discovered Zhang-Yeung inequality.