?
Some Properties of Antistochastic Strings
P. 339–349.
Milovanov A.
In press
Antistochastic strings are those strings that do not have any reasonable statistical explanation. We establish the follow property of such strings: every antistochastic string x is “holographic” in the sense that it can be restored by a short program from any of its part whose length equals the Kolmogorov complexity of x. Further we will show how it can be used for list decoding from erasing and prove that Symmetry of Information fails for total conditional complexity.
In book
Vol. 9139. , Springer, 2015.
Bruno Bauwens, Marchenko M., , in: 21st Conference on Computability in Europe, CiE 2025, Lisbon, Portugal, July 14–18, 2025, Proceedings. Crossroads of Computability and Logic: Insights, Inspirations, and Innovations. (LNCS, volume 15764).: Cham: Springer, 2025. P. 133–142.
Abstract. The even online Kolmogorov complexity of a string x =
x1x2 · · · xn is the minimal length of a program that for all i ≤ n/2,
on input x1x3 · · · x2i−1 outputs x2i. The odd complexity is defined similarly. The sum of the odd and even complexities is called the dialogue
complexity. In ...
Added: December 17, 2025
Semenov A., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 527 № S С. 7–12
The paper proposes a system of definitions for the basic concepts of computability theory that underlie the mathematics of the digital world: algorithm, computability, calculus, object complexity, close to modern undertnding. Hierarchies of the finite and the problem of consistency are considered. ...
Added: December 6, 2025
Semenov A., Shen A., Vereshchagin N., Theory of Probability and its Applications, USA 2024 Vol. 68 No. 4 P. 582–606
The definition of descriptional complexity of finite objects suggested by Kolmogorov and other authors in the mid-1960s is now well known. In addition, Kolmogorov pointed out some approaches to a more fine-grained classification of finite objects, such as the resource-bounded complexity (1965), structure function (1974), and the notion of $(\alpha,\beta)$-stochasticity (1981). Later it turned out ...
Added: January 16, 2025
Vereshchagin N., / Series arXiv "math". 2024.
The fine approach to measure information dependence is based on the total conditional complexity CT(y|x), which is defined as the minimal length of a total program that outputs y on the input x. It is known that the total conditional complexity can be much larger than than the plain conditional complexity. Such strings x, y ...
Added: August 19, 2024
Vereshchagin N., Semenov A., Shen A., Теория вероятностей и ее применения 2023 Т. 68 № 4 С. 719–750
Помимо определения сложности описания конечных объектов (ныне называемой колмогоровской сложностью), Колмогоров наметил несколько способов более детального анализа свойств конечных объектов: сложность с ограничением на ресурсы (1965), структурную функцию (1974), а также понятие (α,β)-стохастичности (1981). Впоследствии выяснилось, что эти понятия по существу эквивалентны (дают одну и ту же кривую в разных координатах).
В этом обзоре мы пытаемся ...
Added: October 25, 2023
Bauwens B. F., Zimand M., Journal of the ACM 2023 Vol. 70 No. 2 Article 9
In a lossless compression system with target lengths, a compressor 𝒞 maps an integer m and a binary string x to an m-bit code p, and if m is sufficiently large, a decompressor 𝒟 reconstructs x from p. We call a pair (m,x) achievable for (𝒞,𝒟) if this reconstruction is successful. We introduce the notion ...
Added: March 22, 2023
Bauwens B. F., Gács P., Romashchenko A. et al., Computability 2022 Vol. 11 No. 3-4 P. 165–185
Finding all linear inequalities for entropies remains an important open question in information theory. For a long time the only known inequalities for entropies of tuples of random variables were Shannon (submodularity) inequalities. Only in 1998 Zhang and Yeung 1998 found the first inequality that cannot be represented as a convex combination of Shannon inequalities, and ...
Added: December 23, 2022
Vereshchagin N., Theoretical Computer Science 2023 Vol. 940 P. 108–122
We consider the network consisting of three nodes 1, 2, 3 connected by two open channels
1 → 2 and 1 → 3. The information present in the node 1 consists of four strings x , y , z , w.
The nodes 2, 3 know x , w and need to know y , z, respectively. ...
Added: December 19, 2022
Milovanov A., , in: Computer Science – Theory and Applications: 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28–July 2, 2021, Proceedings.: Springer, 2021. Ch. 17 P. 283–295.
We combine Solomonoff’s approach to universal prediction with algorithmic statistics and suggest to use the computable measure that provides the best “explanation” for the observed data (in the sense of algorithmic statistics) for prediction. In this way we keep the expected sum of squares of prediction errors bounded (as it was for the Solomonoff’s predictor) ...
Added: August 11, 2021
Bauwens B. F., Blinnikov I., , in: Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, ProceedingsVol. 12159.: Springer, 2020. P. 130–141.
It is known that the normalized algorithmic information distance is not computable and not semicomputable. We show that for all 𝜀<1/2, there exist no semicomputable functions that differ from N by at most 𝜀. Moreover, for any computable function f such that |lim𝑡𝑓(𝑥,𝑦,𝑡)−N(𝑥,𝑦)|≤𝜀 and for all n, there exist strings x, y of length n such that ...
Added: February 5, 2021
Bauwens B. F., , in: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)Vol. 154: Leibniz International Proceedings in Informatics (LIPIcs).: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. P. 46:1–46:14.
Added: March 20, 2020
Vereshchagin N., Theoretical Computer Science 2020 Vol. 809 P. 531–537
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 Science 171 (2001), pp. 47--58]. Namely, we consider the following two complexities of an infinite computable 0-1-sequence $\alpha$: $C^{0'}(\alpha )$, defined as ...
Added: January 17, 2020
Сметанин О. В., Ponomarenko A., В кн.: СБОРНИК ТЕЗИСОВ I научно-практической конференции «Демонстрация, практика внедрения и коммерциализация результатов интеллектуальной деятельности, полученных в рамках выполнения НИОКР. Преодоление технологических барьеров».: М.: ООО "Белый ветер", 2019.
«Покупайка» – это агрегатор цен розничной торговли, реализованный в виде мобильного приложения на платформах iOS и Android. Одной из главных функций системы является оценка привлекательности рыночных предложений для покупателя. Мы считаем предложение привлекательным (выгодным), если предлагаемая цена ниже, чем среднее значение по региону, с учетом текущего местоположения пользователя. В зависимости от разницы между заданным и среднестатистическим значением цены на товар, мы относим предложение к одной из нескольких ценовых ...
Added: October 28, 2019
Shen A., Vereshchagin N., , in: Computability and Complexity.: Berlin: Springer, 2017. P. 669–737.
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 statistical models are better than others. After this notion of a "good model" is introduced, a natural question arises: it is possible that for some piece of data there ...
Added: October 26, 2018
Rubtsov A. A., В кн.: Сборник научных трудов МФТИ "Модели и методы обработки информации".: Долгопрудный: МФТИ, 2016. С. 67–74.
В работе исследуются комбинаторные свойства детерминированных контекстно-свободных языков. Получена новая комбинаторная лемма, схожая по типу с леммами о накачке для КС-языков, а также получены комбинаторные свой ства, следующие из модифицированной известной техники, опирающейся на Кол могоровскую сложность. ...
Added: October 20, 2018
Milovanov A., Theory of Computing Systems 2019 Vol. 63 No. 4 P. 833–848
Algorithmic statistics looks for models of observed data that are good in the following sense: a model is simple (i.e., has small Kolmogorov complexity) and captures all the algorithmically discoverable regularities in the data. However, this idea can not be used in practice as is because Kolmogorov complexity is not computable. In this paper we ...
Added: October 17, 2018
Posobin G. I., Shen A., Andreev M., , in: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)Vol. 117.: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. P. 1–24.
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. This notion was introduced by Vovk and Pavlovic (2016). It turns out that plain stopping time complexity of a binary string x could be equivalently defined as (a) ...
Added: October 11, 2018