### ?

## Some Properties of Antistochastic Strings

P. 339-349.

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

Milovanov A., Theory of Computing Systems 2017 Vol. 61 No. 2 P. 521-535

Algorithmic statistics is a part of algorithmic information theory (Kolmogorov complexity theory) that studies the following task: given a finite object x (say, a binary string), find an `explanation' for it, i.e., a simple finite set that contains x and where x is a `typical element'. Both notions (`simple' and `typical') are defined in terms ...

Added: June 27, 2016

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

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

Milovanov A., , in : Computer Science – Theory and Applications: 12th International Computer Science Symposium in Russia (CSR 2017). Vol. 10304.: Luxemburg : Springer, 2017. P. 232-244.

Algorithmic statistics studies explanations of observed data that are good in the algorithmic sense: an explanation should be simple i.e. should have small Kolmogorov complexity and capture all the algorithmically discoverable regularities in the data. However this idea can not be used in practice because Kolmogorov complexity is not computable.
In this paper we develop algorithmic ...

Added: October 15, 2017

Rubtsov A. A., , in : Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings. : Cham : Springer, 2018. P. 553-565.

We present a new structural lemma for deterministic con- text free languages. From the first sight, it looks like a pumping lemma, because it is also based on iteration properties, but it has significant distinctions that makes it much easier to apply. The structural lemma is a combinatorial analogue of KC-DCF-Lemma (based on Kolmogorov complexity), ...

Added: September 12, 2018

Vereshchagin N., Shen A., Lecture Notes in Computer Science 2017 Vol. 10010 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: February 13, 2017

Milovanov A., , in : Sailing Routes in the World of Computation. : Springer, 2018. P. 287-296.

Algorithmic statistics studies explanations of observed data that are good in the algorithmic sense: an explanation should be simple i.e. should have small Kolmogorov complexity and capture 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 recent years resource-bounded ...

Added: September 4, 2018

Milovanov A., , in : Computer Science – Theory and Applications. 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings. Vol. 9691: Lecture Notes in Computer Science.: Switzerland : Springer, 2016. P. 280-293.

In algorithmic statistics quality of a statistical hypothesis (a model) P for a data x is measured by two parameters: Kolmogorov complexity of the hypothesis and the probability P(x). A class of models SijSij that are the best at this point of view, were discovered. However these models are too abstract. To restrict the class ...

Added: June 27, 2016

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

Vereshchagin N., Theory of Computing Systems 2016 Vol. 58 No. 3 P. 463-481

We introduce the notion of a strong sufficient statistic for a given data string. We show that strong sufficient statistics have better properties than just sufficient statistics. We prove that there are “strange” data strings, whose minimal strong sufficient statistic have much larger complexity than the minimal sufficient statistic. ...

Added: February 7, 2017

Antunes L., Bauwens B. F., Souto A. et al., Theory of Computing Systems 2017 Vol. 60 No. 2 P. 280-298

Sophistication and logical depth are two measures that express how complicated the structure in a string is. Sophistication is defined as the minimal complexity of a computable function that defines a two-part description for the string that is shortest within some precision; the second can be defined as the minimal computation time of a program ...

Added: May 4, 2016

Bienvenu L., Desfontaines D., Shen A., Logical Methods in Computer Science 2016 Vol. 12 No. 2

The halting problem is undecidable --- but can it be solved for "most" inputs? This natural question was considered in a number of papers, in different settings. We revisit their results and show that most of them can be easily proven in a natural framework of optimal machines (considered in algorithmic information theory) using the ...

Added: February 7, 2017

Bauwens B., Makhlin A., Vereshchagin N. et al., Short lists with short programs in short time / . 2013. No. TR13-007.

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on input $x$ a list of ...

Added: December 14, 2013

Bauwens B. F., Theory of Computing Systems 2015 Vol. 58 No. 3 P. 482-501

Added: October 2, 2015

Сметанин О. В., Ponomarenko A., В кн. : СБОРНИК ТЕЗИСОВ I научно-практической конференции «Демонстрация, практика внедрения и коммерциализация результатов интеллектуальной деятельности, полученных в рамках выполнения НИОКР. Преодоление технологических барьеров». : М. : ООО "Белый ветер", 2019.

«Покупайка» – это агрегатор цен розничной торговли, реализованный в виде мобильного приложения на платформах iOS и Android. Одной из главных функций системы является оценка привлекательности рыночных предложений для покупателя. Мы считаем предложение привлекательным (выгодным), если предлагаемая цена ниже, чем среднее значение по региону, с учетом текущего местоположения пользователя. В зависимости от разницы между заданным и среднестатистическим значением цены на товар, мы относим предложение к одной из нескольких ценовых ...

Added: October 28, 2019

Bienvenu L., Muchnik A., Shen A. et al., Limit complexities revisited [once more] / Cornell University. Series math "arxiv.org". 2012. No. 1204.0201.

The main goal of this article is to put some known results in a common perspective and to simplify their proofs. We start with a simple proof of a result of Vereshchagin saying that lim supnC(x|n) equals C0′(x). Then we use the same argument to prove similar results for prefix complexity, a priori probability on binary ...

Added: December 14, 2013

Milovanov A., , in : 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) Leibniz International Proceedings in Informatics (LIPIcs). : Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2016. Ch. 54. P. 1-13.

Algorithmic statistics considers the following problem: given a binary string
x
(e.g., some
experimental data), find a “good” explanation of this data. It uses algorithmic information
theory to define formally what is a good explanation. In this paper we extend this framework in
two directions.
First, the explanations are not only interesting in themselves but also used for prediction: we
want to ...

Added: June 27, 2016

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

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, Proceedings. Vol. 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

Shen A., Uspensky V. A., Vereshchagin N., American Mathematical Society, 2017

Added: October 12, 2017

Vereshchagin N., Мучник А. А., Труды Математического института им. В.А. Стеклова РАН 2011 Т. 274 С. 103-118

Колмогоровская сложность слова $b$ при известном $a$ определяется как минимальная длина программы, перерабатывающей $a$ в $b$. Мы обобщаем это понятие на четверки слов $a,b,c,d$: их совместной условной сложностью $\K((a\to c)\land (b\to d))$ называется минимальная длина программы, перерабатывающей $a$ в $c$, а $b$ в $d$. В работе доказано, что совместная условная сложность не выражается через обычные ...

Added: December 13, 2013

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., Archive for Mathematical Logic 2015 Vol. 54 No. 5 P. 615-629

Joseph Miller [16] and independently Andre Nies, Frank Stephan and Sebastiaan Terwijn [18] gave a complexity characterization of 2-random sequences in terms of plain Kolmogorov complexity C: they are sequences that have infinitely many initial segments with O(1)-maximal plain complexity (among the strings of the same length). Later Miller [17] showed that prefix complexity K ...

Added: October 2, 2015

Vereshchagin N., Milovanov A., , in : 32nd Computational Complexity Conference. : Вадерн : Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017. P. 1-18.

A fundamental notion in Algorithmic Statisticsis that of a stochastic object, i.e., an object having a simple plausible explanation. Informally, a probability distribution is a plausible explanation for x if it looks likely that x was drawn at random with respect to that distribution. In this paper, we suggest three definitions of a plausible statistical ...

Added: October 12, 2017