7 citations · 17 across the 21 of their papers we have counts for
11 papers · 1 filter
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'…
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 $…
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…
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…
m-sophistication
Bruno Bauwens
The m-sophistication of a finite binary string x is introduced as a generalization of some parameter in the proof that complexity of complexity is rare. A probabilistic near suffic…
On the equivalence between minimal sufficient statistics, minimal typical models and initial segments of the Halting sequence
Bruno Bauwens
It is shown that the length of the algorithmic minimal sufficient statistic of a binary string x, either in a representation of a finite set, computable semimeasure, or a computabl…