7 citations · 17 across the 21 of their papers we have counts for
28 papers
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…
Explicit unbalanced 1-expanders with small degree and right size
Bruno Bauwens, Marius Zimand
An explicit graph is given with left size , left degree , right size and -expansion up to~, meaning that every left subset of size $K'…
Online matching games in bipartite expanders: applications to bitprobes and dictionaries with non-adaptive probing
Bruno Bauwens, Marius Zimand
A dictionary is a data structure which stores pairs (key, value). The operation query on input key returns value if the dictionary contains a pair (key, value) and nil otherwise. A…
Key-agreement exists if and only if the "interactive vs non interactive Kolmogorov problem" is not in ioBPP: a short proof
Bruno Bauwens, Bruno Loff
Ball, Liu, Mazor and Pass proved that the existence of key-agreement protocols is equivalent to the hardness of a certain problem about interactive Kolmogorov complexity. We genera…
Space-bounded online Kolmogorov complexity is additive
Bruno Bauwens, Maria Marchenko
The even online Kolmogorov complexity of a string is the minimal length of a program that for all , on input outputs $…
Online matching games in bipartite expanders: Hall-type results and applications to non-blocking connectors
Bruno Bauwens, Marius Zimand
The classical Hall Theorem shows the equivalence between \emph{offline} matching in bipartite graphs and a certain expansion property. We show that lossless expansion implies effic…
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…
Conditional probabilities and van Lambalgen theorem revisited
Bruno Bauwens, Alexander Shen, Hayato Takahashi
The definition of conditional probability in case of continuous distributions was an important step in the development of mathematical theory of probabilities. How can we define th…
Uniform van Lambalgen's theorem fails for computable randomness
Bruno Bauwens
We show that there exists a bitsequence that is not computably random for which its odd bits are computably random and its even bits are computably random relative to the odd bits.…
Van Lambalgen's theorem fails for some computable measure
Bruno Bauwens
Van Lambalgen's theorem states that a pair of bitsequences is Martin-Löf random if and only if is Martin-Löf random and is Martin-Löf random relative to . In [In…
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…
Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity
Bruno Bauwens, Alexander Shen
Peter Gacs showed (Gacs 1974) that for every n there exists a bit string x of length n whose plain complexity C(x) has almost maximal conditional complexity relative to x, i.e., C(…
An additivity theorem for plain Kolmogorov complexity
Bruno Bauwens, Alexander Shen
We prove the formula C(a,b) = K(a|C(a,b)) + C(b|a,C(a,b)) + O(1) that expresses the plain complexity of a pair in terms of prefix and plain conditional complexities of its componen…