Zobrazeno 1 - 10
of 101
pro vyhledávání: '"Vereshchagin, Nikolay"'
Half-duplex communication complexity with adversary was defined in [Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A. V. Half-Duplex Communication Complexity, ISAAC 2018.] Half-duplex communication protocols generalize classical protocols defined b
Externí odkaz:
http://arxiv.org/abs/2405.16881
Autor:
Vereshchagin, Nikolay
We define a new family of non-periodic tilings with square tiles that is mutually locally derivable with some family of tilings with isosceles right triangles. Both families are defined by simple local rules, and the proof of their non-periodicity is
Externí odkaz:
http://arxiv.org/abs/2307.16134
Autor:
Vereshchagin, Nikolay
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 b
Externí odkaz:
http://arxiv.org/abs/2307.04530
The last theme of Kolmogorov's mathematics research was algorithmic theory of information, now often called Kolmogorov complexity theory. There are only two main publications of Kolmogorov (1965 and 1968-1969) on this topic. So Kolmogorov's ideas tha
Externí odkaz:
http://arxiv.org/abs/2303.13185
Autor:
Vereshchagin, Nikolay
We consider the network consisting of three nodes $1, 2, 3$ connected by two open channels $1\rightarrow 2$ and $1\rightarrow 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 $
Externí odkaz:
http://arxiv.org/abs/2108.01685
Autor:
Vereshchagin, Nikolay
We study a family of substitution tilings with similar right triangles of two sizes which is obtained using the substitution rule introduced in [Danzer, L. and van Ophuysen, G. A species of planar triangular tilings with inflation factor $\sqrt{-\tau
Externí odkaz:
http://arxiv.org/abs/2007.10658
Autor:
Vereshchagin, Nikolay
In this paper we consider Levin's notion of mutual information in infinite 0-1-sequences, as defined in [Leonid Levin. Laws of Information Conservation (Nongrowth) and Aspects of the Foundation of Probability Theory. Problems of information transmiss
Externí odkaz:
http://arxiv.org/abs/1911.05447
Autor:
Vereshchagin, Nikolay
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 co
Externí odkaz:
http://arxiv.org/abs/1902.01279
Autor:
Vereshchagin, Nikolay
Publikováno v:
In Theoretical Computer Science 9 January 2023 940 Part B:108-122
Autor:
Vereshchagin, Nikolay, Shen, Alexander
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
Externí odkaz:
http://arxiv.org/abs/1504.04950