Collection Nexus Trimester - 2016 - Central Workshop
Organizer(s)
Date(s)
03/05/2024
Asymmetry of online Kolmogorov complexity
In order for a source to reveal a string x, it needs to store at least C(x) bits of information (C(x) represents the Kolmogorov complexity). Imagine, two sources need to reveal complementary parts of x in two stages: a first machine writes some bits of x on a common communication tape, and afterwards, a second machine writes the remaining bits. Symmetry of information implies that with an optimal encoding the total amount of bits stored in both sources can be as small as C(x). We show that if the sources need to reveal their information about x in small chunks in alternating turns, symmetry of information is violated: it might happen that both sources need to store almost all information about x. We also show that the order in which the small chunks of information is revealed is important. The results can be connected to a rather speculative application to the inference of causal relations in time series.
