The second Towards Data Science post references this paper, which is also the main reference through which Levin’s result is mentioned in the first paper you post. So I assume reading these references should be enough to get the gist.
I think what can be found in that book is a proof of the coding theorem, which is different from the claim you call the “Levin bound” here, I think. What you call the Levin bound is proved in this paper and has a much simpler proof than the coding theorem.
Do you have a good reference for the Levin bound? My attempts at finding a relevant paper all failed.
The second Towards Data Science post references this paper, which is also the main reference through which Levin’s result is mentioned in the first paper you post. So I assume reading these references should be enough to get the gist.
There is a proof of it in “An Introduction to Kolmogorov Complexity and Its Applications” by Ming Li & Paul Vitanyi.
I think what can be found in that book is a proof of the coding theorem, which is different from the claim you call the “Levin bound” here, I think. What you call the Levin bound is proved in this paper and has a much simpler proof than the coding theorem.