loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
Andrei Romashchenko, Institute for Information Transmission Problems
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.
Citation:
Andrei Romashchenko, "Extracting the Mutual Information for a Triple of Binary Strings," ccc, pp.221, 18th Annual IEEE Conference on Computational Complexity (CCC'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.