### ?

## On Algorithmic Statistics for Space-Bounded Algorithms

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 statistics using space-bounded Kolmogorov complexity. We prove an analogue of one of the main result of ‘classic’ algorithmic statistics (about the connection between optimality and randomness deficiences). The main tool of our proof is the Nisan-Wigderson generator.

Publication based on the results of:

### In book

Vol. 10304. , Luxemburg: Springer, 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., 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

Alexander Shen, 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 10th International Computer Science Symposium in Russia, CSR 2015. Vol. 9139.: Springer, 2015.. P. 339-349.

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 ...

Added: June 27, 2016

Vereshchagin N., A Shen, 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., 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

Bauwens B. F., Alexander Shen, Theory of Computing Systems 2013 Vol. 52 No. 2 P. 297-302

Added: October 2, 2015

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

Added: October 2, 2015

Vereshchagin N., , in: CSR 2014 : 9th International Computer Science Symposium in Russia. Proceedings. Vol. 8476.: Berlin: Springer, 2014.. P. 365-374.

The paper [Harry Buhrman, Michal Kouck ́, Nikolay Vereshcha y
gin. Randomized Individual Communication Complexity. IEEE Con ference on Computational Complexity 2008: 321-331] considered com munication complexity of the following problem. Alice has a bi nary string x and Bob a binary string y, both of length n, and they
want to compute or approximate Kolmogorov complexity C(x|y) of
x conditional to ...

Added: October 6, 2014

Vereshchagin N., Bauwens B. F., Anton Makhlin et al., Computational Complexity 2018 Vol. 27 No. 1 P. 31-61

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: April 22, 2017

Laurent Bienvenu, Damien Desfontaines, Alexander Shen, 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

Bruno Bauwens, Anton Makhlin, 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

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

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

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

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

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

Bauwens B. F., Alexander Shen, Journal of Symbolic Logic 2013 Vol. 79 No. 2 P. 620-632

Added: October 2, 2015

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

Laurent Bienvenu, Andrej A. Muchnik, Alexander Shen 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

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

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

Alexander Shen, Vladimir Andreevich Uspensky, Vereshchagin N., American Mathematical Society, 2017

Added: October 12, 2017