Zobrazeno 1 - 10
of 47
pro vyhledávání: '"Nikolai K. Vereshchagin"'
Autor:
Nikolai K. Vereshchagin
Publikováno v:
Theory of Computing Systems. 61:1440-1450
Let {φ p } be an optimal Godel 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 len
Publikováno v:
IEEE Transactions on Information Theory
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2018, 64 (5), pp.3610-3615. ⟨10.1109/TIT.2018.2806486⟩
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2018, 64 (5), pp.3610-3615. ⟨10.1109/TIT.2018.2806486⟩
We show that the inequality $H(A | B,X) + H(A | B,Y) \leqslant H(A | B)$ for jointly distributed random variables $A,B,X,Y$ , which does not hold in general case, holds under some natural condition on the support of the probability distribution of $A
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::11a13b0377d2992dff6eca31e31773e7
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01793775
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01793775
Publikováno v:
IEEE Transactions on Information Theory, 56(7), 3438-3454. Institute of Electrical and Electronics Engineers Inc.
We examine the structure of families of distortion balls from the perspective of Kolmogorov complexity. Special attention is paid to the canonical rate-distortion function of a source word which returns the minimal Kolmogorov complexity of all distor
Autor:
Nikolai K. Vereshchagin
Publikováno v:
Information Processing Letters. 103:34-39
Solovay [R.M. Solovay, On random R.E. sets, in: A.I. Arruda, N.C.A. da Costa, R. Chaqui (Eds.), Non-Classical Logics, Model Theory and Computability, North-Holland, Amsterdam, 1977, pp. 283-307] has proved that the minimal length of a program enumera
Publikováno v:
European Journal of Combinatorics, 28, 134-144
Our main result implies the following easily formulated statement. The set of edges E of every finite bipartite graph can be split into poly(log |E|) subsets so that all the resulting bipartite graphs are almost regular. The latter means that the rat
Autor:
Bruno Durand, Nikolai K. Vereshchagin
Publikováno v:
Information Processing Letters. 91:263-269
Asarin [Theory Probab. Appl. 32 (1987) 507-508] showed that any finite sequence with small randomness deficiency has the stability property of the frequency of 1s in their subsequences selected by simple Kolmogorov-Loveland selection rules. Roughly s
Publikováno v:
IEEE Transactions on Information Theory, 50(12), 3265-3290. Institute of Electrical and Electronics Engineers Inc.
In 1974, Kolmogorov proposed a nonprobabilistic approach to statistics and model selection. Let data be finite binary strings and models be finite sets of binary strings. Consider model classes consisting of models of given maximal (Kolmogorov) compl
Publikováno v:
Information and Computation. 184:229-241
Consider a sender transmitting a given sequence of bits simultaneously through m binary symmetric channels with error probabilities e1,..... em such that 0 ≤ ei < 1/2 for each i = 1, ..... m. The receiver can base its guess for the true transmitted
Publikováno v:
Theoretical Computer Science. 290:1987-1996
In this paper, we investigate refined definition of random sequences. Classical definitions (Martin-Löf tests of randomness, uncompressibility, unpredictability, or stochasticness) make use of the notion of algorithm. We present alternative definiti
Publikováno v:
Communications in Information and Systems. 2:147-166
In this paper we prove a countable set of non-Shannon-type linear information inequalities for entropies of discrete random variables, i.e., information inequalities which cannot be reduced to the "basic" inequality I(X : Y |Z) 0. Our results general