×

A random oracle does not help extract the mutual information. (English) Zbl 1173.68541

Ochmański, Edward (ed.) et al., Mathematical foundations of computer science 2008. 33rd international symposium, MFCS 2008, Toruń Poland, August 25–29, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85237-7/pbk). Lecture Notes in Computer Science 5162, 527-538 (2008).
Summary: Assume a tuple of words \(\bar x =\langle x_1,\ldots,x_n\rangle\) has negligible mutual information with another word \(y\). Does this mean that properties of Kolmogorov complexity for \(\bar x\) do not change significantly if we relativize them conditional to \(y\)? This question becomes very nontrivial when we try to formalize it. We investigate this question for a very particular kind of properties: we show that a random (conditional to \(\bar x\)) oracle \(y\) cannot help extract the mutual information from \(x _{i }\)’s.
For the entire collection see [Zbl 1154.68021].

MSC:

68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
PDFBibTeX XMLCite
Full Text: DOI