Source author record

Nikolay Vereshchagin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Information Theory math.IT math.LO Computer Science and Game Theory

Catalog footprint

Research overview

3works

4topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Algorithmic statistics revisited

The mission of statistics is to provide adequate statistical hypotheses (models) for observed data. But what is an "adequate" model? To answer this question, one needs to use the notions of algorithmic information theory. It turns out that for every data string $x$ one can naturally define "stochasticity profile", a curve that represents a trade-off between complexity of a model and its adequacy. This curve has four different equivalent definitions in terms of (1)~randomness deficiency, (2)~minimal description length, (3)~position in the lists of simple strings and (4)~Kolmogorov complexity with decompression time bounded by busy beaver function. We present a survey of the corresponding definitions and results relating them to each other.

preprint2014arXiv

Short lists with short programs for functions

Let $\{ϕ_p\}$ be an optimal Gödel numbering of the family of computable functions (in Schnorr's sense), where $p$ ranges over binary strings. Assume that a list of strings $L(p)$ is computable from $p$ and for all $p$ contains a $ϕ$ -program for $ϕ_p$ whose length is at most $\varepsilon$ bits larger that the length of the shortest $ϕ$ -program for $ϕ_p$ . We show that for infinitely many $p$ the list $L(p)$ must have $2^{|p|-\varepsilon-O(1)}$ strings. Here $\varepsilon$ is an arbitrary function of $p$ .

preprint2010arXiv

Game interpretation of Kolmogorov complexity

The Kolmogorov complexity function K can be relativized using any oracle A, and most properties of K remain true for relativized versions. In section 1 we provide an explanation for this observation by giving a game-theoretic interpretation and showing that all "natural" properties are either true for all sufficiently powerful oracles or false for all sufficiently powerful oracles. This result is a simple consequence of Martin's determinacy theorem, but its proof is instructive: it shows how one can prove statements about Kolmogorov complexity by constructing a special game and a winning strategy in this game. This technique is illustrated by several examples (total conditional complexity, bijection complexity, randomness extraction, contrasting plain and prefix complexities).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.