5 papers
Kolmogorov complexity as a combinatorial tool
Alexander Shen
Kolmogorov complexity is often used as a convenient language for counting and/or probabilistic existence proofs. However, there are some applications where Kolmogorov complexity is…
Comparing angles in Euclid's Elements
Alexander Shen
The exposition in Euclid's Elements contains an obvious gap (seemingly unnoticed by most commentators): he often compares not just angles, but *groups* of angles, and at the same t…
Conditional normality and finite-state dimensions revisited
Alexander Shen
The notion of a normal bit sequence was introduced by Borel in 1909; it was the first definition of an individual random object. Normality is a weak notion of randomness requiring…
Israil Moiseevich Gelfand [In Russian]
Alexander Shen
I was lucky to meet (and even cooperate at some extent) with Israel M. Gelfand, and tried to write down (mainly in 2003-2013) my recollections about his work style and lessons I le…
K-trivial, K-low and MLR-low sequences: a tutorial
Laurent Bienvenu, Alexander Shen
A remarkable achievement in algorithmic randomness and algorithmic information theory was the discovery of the notions of K-trivial, K-low and Martin-Lof-random-low sets: three dif…