|
Published Articles >> Table of Contents >> Abstract
18th Annual IEEE Conference on Computational Complexity (CCC'03)
p. 221
Extracting the Mutual Information for a Triple of Binary Strings
Andrei Romashchenko, Institute for Information Transmission Problems
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214422
Send link to a friend
| Abstract |
|
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.
|
 Additional Information
|
Citation:
Andrei Romashchenko,
"Extracting the Mutual Information for a Triple of Binary Strings,"
complexity,
p. 221,
18th Annual IEEE Conference on Computational Complexity (CCC'03),
2003
|
|
