3 citations · 3 across the 5 of their papers we have counts for
7 papers
Maximal Kolmogorov Complexity in a Hamming Ball
Alexander Kozachinskiy, Nikolay Vereshchagin
The minimal Kolmogorov complexity of a string within Hamming distance r of a given string x is the algorithmic rate-distortion function of x, and Vereshchagin and Vitanyi character…
Matching Rules for Substitution and Hierarchical Tilings for any Substitution with Finite Local Complexity
Nikolay Vereshchagin
The Goodman-Strauss theorem states that for ``almost every'' substitution , the family of substitution tilings is sofic, that is, it can be defined by local matching rules for s…
Goodman-Strauss theorem revisited
Nikolay Vereshchagin
The Goodman-Strauss theorem states that for ``almost every" substitution, the family of substitution tilings is sofic, that is, it can be defined by local rules for some decoration…
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…
Descriptive Complexity of Computable Sequences Revisited
Nikolay Vereshchagin
The purpose of this paper is to answer two questions left open in [B. Durand, A. Shen, and N. Vereshchagin, Descriptive Complexity of Computable Sequences, Theoretical Computer Sci…
Short lists with short programs for functions
Nikolay Vereshchagin
Let be an optimal Gödel numbering of the family of computable functions (in Schnorr's sense), where ranges over binary strings. Assume that a list of strings i…
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…