Asymmetry of online Kolmogorov complexity
150 views · Published 14 March 2016 · 29:06 · Indexed 10 November 2026
Channel: Institut Henri Poincaré · 2016 · Science & Technology
By Bruno Bauwens (Higher School of Economics) Abstract: In order for a source to reveal a string , it needs to store at least [Math Processing Error] bits of information ([Math Processing Error] represents the Kolmogorov complexity). Imagine, two sources need to reveal complementary parts of [Math Processing Error] in two stages: a first machine writes some bits of [Math Processing Error] 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 [Math Processing Error]. We show that if the sources need to reveal their information about [Math Processing Error] in small chunks in alternating turns, symmetry of information is violated: it might happen that both sources need to store almost all information about [Math Processing Error]. 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.
More from this channel
-
29:47
10 ans du Groupe Calcul : Histoire du Calcul - Introduction
-
52:14
Gauss, Jacobi, Seidel, Richardson, Krylov: the Invention of Iterative Methods
-
55:33
Les "invariants arithmétiques" de H. Poincaré
-
1:08:53
Henri Poincaré, a founding father of the modern theory of PDEs
-
57:13
Sympletic topology from Poincaré to Gromov
-
57:35
Structural Realism, Then and Now
-
46:26
Poincaré inequalities in probability and geometric analysis
-
1:02:05
On the contributions of Henri Poincaré to modern geophysics...