Coding in the fork network in the framework of Kolmogorov complexity

Abstract

Many statements from the classic information theory (the theory of Shannon's entropy) have natural counterparts in the algorithmic information theory (in the framework of Kolmogorov complexity). In this paper we discuss one simple instance of the parallelism between Shannon's and Kolmogorov's theories: we prove in the setting of Kolmogorov complexity a version of Wolf's characterization of admissible rates for the fork network.

v2: fixed a mistake in the proof of theorem 4