1 citations · 1 across the 3 of their papers we have counts for
6 papers
Precise Expression for the Algorithmic Information Distance
Bruno Bauwens
We consider the notion of information distance between two objects and introduced by Bennett, Gács, Li, Vitányi, and Zurek in 1998 as the minimal length of a program that c…
The normalized algorithmic information distance can not be approximated
Bruno Bauwens, Ilya Blinnikov
It is known that the normalized algorithmic information distance is not computable and not semicomputable. We show that for all , there exist no semicomputable function…
Universal almost optimal compression and Slepian-Wolf coding in probabilistic polynomial time
Bruno Bauwens, Marius Zimand
In a lossless compression system with target lengths, a compressor maps an integer and a binary string to an -bit code , and if is sufficiently large,…
Information Distance Revisited
Bruno Bauwens, Alexander Shen
We consider the notion of information distance between two objects x and y introduced by Bennett, Gács, Li, Vitanyi, and Zurek [1] as the minimal length of a program that computes…
Optimal probabilistic polynomial time compression and the Slepian-Wolf theorem: tighter version and simple proofs
Bruno Bauwens
We give simplify the proofs of the 2 results in Marius Zimand's paper "Kolmogorov complexity version of Slepian-Wolf coding, proceedings of STOC 2017, p22--32". The first is a univ…
Additivity of on-line decision complexity is violated by a linear term in the length of a binary string
Bruno Bauwens
We show that there are infinitely many binary strings z, such that the sum of the on-line decision complexity of predicting the even bits of z given the previous uneven bits, and t…