ECCC-Report TR14-133https://eccc.weizmann.ac.il/report/2014/133Comments and Revisions published for TR14-133en-usFri, 24 Oct 2014 10:56:57 +0300
Paper TR14-133
| Mutual Dimension |
Adam Case,
Jack H. Lutz
https://eccc.weizmann.ac.il/report/2014/133We define the lower and upper mutual dimensions $mdim(x:y)$ and $Mdim(x:y)$ between any two points $x$ and $y$ in Euclidean space. Intuitively these are the lower and upper densities of the algorithmic information shared by $x$ and $y$. We show that these quantities satisfy the main desiderata for a satisfactory measure of mutual algorithmic information. Our main theorem, the data processing inequality for mutual dimension, says that, if $f:\mathbb{R}^m \rightarrow \mathbb{R}^n$ is computable and Lipschitz, then the inequalities $mdim(f(x):y) \leq mdim(x:y)$ and $Mdim(f(x):y) \leq Mdim(x:y)$ hold for all $x \in \mathbb{R}^m$ and $y \in \mathbb{R}^t$. We use this inequality and related inequalities that we prove in like fashion to establish conditions under which various classes of computable functions on Euclidean space preserve or otherwise transform mutual dimensions between points.Fri, 24 Oct 2014 10:56:57 +0300https://eccc.weizmann.ac.il/report/2014/133