PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Andrei Nikolaevich Kolmogorov
p. 1

Kolmogorov $\varepsilon$-Entropy in the Problems on Global Attractors for Evolution Equations of Mathematical Physics
M. I. Vishik and V. V. Chepyzhov
pp. 2–20

Abstract—We study the Kolmogorov $\varepsilon$-entropy and the fractal dimension of global attractors for autonomous and nonautonomous equations of mathematical physics. We prove upper estimates for the $\varepsilon$-entropy and fractal dimension of the global attractors of nonlinear dissipative wave equations.

Kolmogorov’s Contributions to the Foundations of Probability
V. G. Vovk and G. R. Shafer
pp. 21–31

Abstract—Andrei Nikolaevich Kolmogorov was the foremost contributor to the mathematical and philosophical foundations of probability in the twentieth century, and his thinking on the topic is still potent today. In this article we first review the three stages of Kolmogorov’s work on the foundations of probability: (1) his formulation of measure-theoretic probability, 1933; (2) his frequentist theory of probability, 1963; and (3) his algorithmic theory of randomness, 1965–1987. We also discuss another approach to the foundations of probability, based on martingales, which Kolmogorov did not consider.

Problems of Robustness for Universal Coding Schemes
V. V. V'yugin
pp. 32–46

Abstract—The Lempel–Ziv universal coding scheme is asymptotically optimal for the class of all stationary ergodic sources. A problem of robustness of this property under small violations of ergodicity is studied. The notion of deficiency of algorithmic randomness is used as a measure of disagreement between data sequence and probability measure. We prove that universal compression schemes from a large class are nonrobust in the following sense: If the randomness deficiency grows arbitrarily slowly on initial fragments of an infinite sequence, then the property of asymptotic optimality of any universal compression algorithm can be violated. Lempel–Ziv compression algorithms are robust on infinite sequences generated by ergodic Markov chains when the randomness deficiency of their initial fragments of length $n$ grows as $o(n)$.

Existence and Uniqueness of Solutions of a Quasilinear Approximation of the 3D Navier–Stokes System
E. I. Dinaburg and Ya. G. Sinai
pp. 47–50

Abstract—For the quasilinear approximation of the 3D Navier–Stokes system proposed earlier by the authors in [Moscow Math. J., 2001, vol. 1, no. 3, pp. 381–388], some conditions of solution regularity are considered and the theorem on existence and uniqueness of the Cauchy problem for some class of initial data is proved.

An Estimation Problem for Quasilinear Stochastic Partial Differential Equations
I. A. Ibragimov
pp. 51–77

Abstract—A problem of estimating a functional parameter $\theta (x)$ and functionals $\Phi (\theta)$ based on observation of a solution $u_{\varepsilon} (t,x)$ of the stochastic partial differential equation $$ du_{\varepsilon} (t)=\sum\limits_{|k|\leq 2p} a_k D_x^k u_{\varepsilon}\,dt+\theta (x)g(u_{\varepsilon},t,x)+\varepsilon\,dw(t) $$ is considered. The asymptotic problem setting, as the noise intensity $\varepsilon\to 0$, is investigated.

Zeros and Local Extrema of Trigonometric Sums
A. A. Karatsuba
pp. 78–91

Abstract—Theorems on the number of zeros and number of local extrema of trigonometric sums, in particular, Gauss and Weyl sums, are proved.

The Tale of One-Way Functions
L. A. Levin
pp. 92–103

Abstract—The existence of one-way functions (owf) is arguably the most important problem in computer theory. The article discusses and refines a number of concepts relevant to this problem. For instance, it gives the first combinatorial complete owf, i.e., a function which is one-way if any function is. There are surprisingly many subtleties in basic definitions. Some of these subtleties are discussed or hinted at in the literature and some are overlooked. Here, a unified approach is attempted.

Indefinite Knowledge about an Object and Accuracy of Its Recovery Methods
G. G. Magaril-Il'yaev, K. Yu. Osipenko, and V. M. Tikhomirov
pp. 104–118

Abstract—An approach to the problem of optimal recovery of functionals and operators on classes of functions under the conditions of infinite knowledge of functions themselves is discussed. The capabilities of this approach are demonstrated in a number of examples. In the end of the paper, a general result about optimal recovery of linear functionals is given.

On the Role of the Law of Large Numbers in the Theory of Randomness
An. A. Muchnik and A. L. Semenov
pp. 119–147

Abstract—In the first part of the article, we answer Kolmogorov’s question (stated in 1963 in [Sankhyā, Indian J. Statist., Ser. A, 1963, vol. 25, no. 4, pp. 369–376]) about exact conditions for the existence of random generators. Kolmogorov theory of complexity allowed for a precise definition of the notion of randomness for an individual sequence of zeros and ones. For infinite sequences, the property of randomness is a binary property, a sequence can be random or not. For finite sequences, we can solely speak about a continuous property, a measure of randomness. Is it possible to measure randomness of a sequence $\boldsymbol{t}$ by the extent to which the law of large numbers is satisfied in all subsequences of $\boldsymbol{t}$ obtained in an “admissible way”? The case of infinite sequences was studied in [Theor. Comp. Sci., 1998, vol. 207, no. 1–2, pp. 263–317]. As a measure of randomness (or, more exactly, of nonrandomness) of a finite sequence, we consider the specific deficiency of randomness $\delta$ (Definition 5). In the second part of this paper, we prove that the function $\delta/\ln(1/\delta)$ characterizes the connections between randomness of a finite sequence and the extent to which the law of large numbers is satisfied.

A Criterion for Extractability of Mutual Information for a Triple of Strings
A. E. Romashchenko
pp. 148–157

Abstract—We say that the mutual information of a triple of binary strings $a,b,c$ can be extracted if there exists a string $d$ such that $a$, $b$, and $c$ are independent given $d$, and $d$ is simple conditional to each of the strings $a$, $b$, and $c$. It is proved that the mutual information between $a$, $b$, and $c$ can be extracted if and only if the values of the conditional mutual informations $I(a:b\,|\,c)$, $I(a:c\,|\,b)$, and $I(b:c\,|\,a)$ are negligible. The proof employs a non-Shannon-type information inequality (a generalization of the recently discovered Zhang–Yeung inequality).