A Random Oracle Does Not Help Extract the Mutual Information

DOI10.1007/978-3-540-85238-4_43MaRDI QIDQ3599155zbMATH OpenOpenAlexFDO

Authors Andrej Muchnik, Andrei Romashchenko

Publication date 3 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85238-4_43

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Stability of properties of Kolmogorov complexity under relativization
• On joint conditional complexity (entropy)
• Pairs of words with nonmaterializable mutual information
• On common information
• Proofs of conservation inequalities for Levin's notion of mutual information of 1974

Cited in

(4)

• Pairs of words with nonmaterializable mutual information
• A criterion for extractability of mutual information for a triple of strings
• Stability of properties of Kolmogorov complexity under relativization
• Relative complexity of random walks in random sceneries

This page was built for publication: A Random Oracle Does Not Help Extract the Mutual Information

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3599155)