7 citations · 17 across the 21 of their papers we have counts for
11 papers · 1 filter
Solomonoff induction of selected bits and online classification
Bruno Bauwens, German Kuznetsov
Solomonoff induction is a general solution for sequence prediction that started the field of algorithmic information theory around 1960. Let be the universal semimeasure. After…
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…
Universal codes in the shared-randomness model for channels with general distortion capabilities
Bruno Bauwens, Marius Zimand
We put forth new models for universal channel coding. Unlike standard codes which are designed for a specific type of channel, our most general universal code makes communication r…
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…
Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs
Bruno Bauwens
Joseph Miller [16] and independently Andre Nies, Frank Stephan and Sebastiaan Terwijn [18] gave a complexity characterization of 2-random sequences in terms of plain Kolmogorov com…
Asymmetry of the Kolmogorov complexity of online predicting odd and even bits
Bruno Bauwens
Symmetry of information states that . We show that a similar relation for online Kolmogorov complexity does not hold. Let the even (online Ko…
Sophistication vs Logical Depth
Luís Antunes, Bruno Bauwens, Andre Souto +1
Sophistication and logical depth are two measures that express how complicated the structure in a string is. Sophistication is defined as the minimal complexity of a computable fun…
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…