7 citations · 17 across the 21 of their papers we have counts for
7 papers · 1 filter
Upper semicomputable sumtests for lower semicomputable semimeasures
Bruno Bauwens
A sumtest for a discrete semimeasure is a function mapping bitstrings to non-negative rational numbers such that \[ \sum P(x)f(x) \le 1 \,. \] Sumtests are the discrete ana…
Linear list-approximation for short programs (or the power of a few random bits)
Bruno Bauwens, Marius Zimand
A -short program for a string is a description of of length at most , where is the Kolmogorov complexity of . We show that there exists a randomized…
Relating and contrasting plain and prefix Kolmogorov complexity
Bruno Bauwens
In [3] a short proof is given that some strings have maximal plain Kolmogorov complexity but not maximal prefix-free complexity. The proof uses Levin's symmetry of information, Lev…
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…
Short lists with short programs in short time
Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin +1
Given a machine , a -short program for is a string such that and the length of is bounded by + (the length of a shortest program for ). We show th…