70 citations · 229 across the 50 of their papers we have counts for
8 papers · 1 filter
Plain stopping time and conditional complexities revisited
Mikhail Andreev, Gleb Posobin, Alexander Shen
In this paper we analyze the notion of "stopping time complexity", informally defined as the amount of information needed to specify when to stop while reading an infinite sequence…
Algorithmic statistics: forty years later
Nikolai Vereshchagin, Alexander Shen
Algorithmic statistics has two different (and almost orthogonal) motivations. From the philosophical point of view, it tries to formalize how the statistics works and why some stat…
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…
Fixed-point tile sets and their applications
Bruno Durand, Andrei Romashchenko, Alexander Shen
An aperiodic tile set was first constructed by R. Berger while proving the undecidability of the domino problem. It turned out that aperiodic tile sets appear in many topics rangin…
Variations on Muchnik's Conditional Complexity Theorem
Daniil Musatov, Andrei Romashchenko, Alexander Shen
Muchnik's theorem about simple conditional descriptions states that for all strings and there exists a short program transforming to that has the least possible…
Limit complexities revisited
Laurent Bienvenu, Andrej Muchnik, Alexander Shen +1
The main goal of this paper is to put some known results in a common perspective and to simplify their proofs. We start with a simple proof of a result from (Vereshchagin, 2002) sa…