70 citations · 229 across the 50 of their papers we have counts for
17 papers · 1 filter
Kolmogorov Last Discovery? (Kolmogorov and Algorithmic Statictics)
Alexey Semenov, Alexander Shen, Nikolay Vereshchagin
The last theme of Kolmogorov's mathematics research was algorithmic theory of information, now often called Kolmogorov complexity theory. There are only two main publications of Ko…
Gács-Kučera's Theorem Revisited by Levin
George Barmpalias, Alexander Shen
Leonid Levin (arxiv.org/abs/cs/0503039v14, p.7) published a new (and very nice) proof of Gács-Kučera's theorem that occupies only a few lines when presented in his style. We try to…
Complexity of majorants
Alexander Shen
The minimal Kolmogorov complexity of a total computable function that exceeds everywhere all total computable functions of complexity at most , is . If we replace "e…
Priority arguments and separation problems
Alexander Shen
Different constructions in the recursion theory use the so-called priority arguments. A general scheme was suggested by A.~Lachlan. Based on his work, we define the notion of a pri…
Axiomatic approach to the theory of algorithms and relativized computability
Alexander Shen
It is well known that many theorems in recursion theory can be "relativized". This means that they remain true if partial recursive functions are replaced by functions that are par…
Dimension 1 sequences are close to randoms
Noam Greenberg, Joe Miller, Alexander Shen +1
We show that a sequence has effective Hausdorff dimension 1 if and only if it is coarsely similar to a Martin-Löf random sequence. More generally, a sequence has effective dimensio…