On Algorithmic Statistics for Space-bounded Algorithms

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

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2019-05, Vol.63 (4), p.833-848
Main Author: Milovanov, Alexey
Format: Article
Language:English
Subjects:
Algorithms
Complexity
Computer Science
Computer Science Symposium in Russia
Statistics
Theory of Computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 develop an algorithmic version of algorithmic statistics that uses space-bounded Kolmogorov complexity. We prove a space-bounded version of a basic result from “classical” algorithmic statistics, the connection between optimality and randomness deficiences. The main tool is the Nisan–Wigderson pseudo-random generator. An extended abstract of this paper was presented at the 12th International Computer Science Symposium in Russia (Milovanov 10 ).
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-018-9845-6