PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Code Spectrum and the Reliability Function: Binary Symmetric Channel
M. V. Burnashev
pp. 263–281

Abstract—A new approach for upper bounding the channel reliability function using the code spectrum is described. It allows to treat both the low and high rate cases in a unified way. In particular, previously known upper bounds are improved, and a new derivation of the sphere-packing bound is presented.

On the Structure of Optimal Sets for a Quantum Channel
M. E. Shirokov
pp. 282–297

Abstract—Special sets of states, called optimal, which are related to the Holevo capacity and to the minimal output entropy of a quantum channel, are considered. By methods of convex analysis and operator theory, structural properties of optimal sets and conditions of their coincidence are explored for an arbitrary channel. It is shown that strong additivity of the Holevo capacity for two given channels provides projective relations between optimal sets for the tensor product of these channels and optimal sets for the individual channels.

On the Reliability Exponent of the Additive Exponential Noise Channel
Y. Ovadia and S. I. Bross
pp. 298–318

Abstract—We study the reliability exponent of the additive exponential noise channel (AENC) in the absence as well as in the presence of noiseless feedback. For rates above the critical rate, the fixed-transmission-time reliability exponent of the AENC is completely determined, while below the critical rate an expurgated exponent is obtained. Using a fixed-block-length code ensemble (with block length denoting the number of recorded departures), we obtain a lower bound on the random-transmission-time reliability exponent of the AENC. Finally, with a variable-block-length code ensemble, a lower bound on the random-transmission-time zero-error capacity of the AENC with noiseless feedback is obtained.

An Extension Theorem for Arcs and Linear Codes
I. Landjev and A. Rousseva
pp. 319–329

Abstract—We prove the following generalization to the extension theorem of Hill and Lizak: For every nonextendable linear $[n,k,d]_q$ code, $q=p^s$, $(d,q)=1$, we have $$ \sum_{i\not\equiv 0,d\: \pmod{q}} A_i\gt q^{k-3} r(q), $$ where $q+r(q)+1$ is the smallest size of a nontrivial blocking set in $\operatorname{PG}(2,q)$. This result is applied further to rule out the existence of some linear codes over $\mathbb{F}_4$ meeting the Griesmer bound.

On-line Estimation of Smooth Signals with Partial Observation
P. L. Chow and R. Z. Khasminskii
pp. 330–339

Abstract—The paper concerns the estimation of a smooth signal $S(t)$ and its derivatives in the presence of a noise depending on a small parameter $\varepsilon$ based on a partial observation. A nonlinear Kalman-type filter is proposed to perform on-line estimation. For the signal $S$ in a given class of smooth functions, the convergence rate for the estimation risks, as $\varepsilon\to 0$, is obtained. It is proved that such rates are optimal in a minimax sense. In contrast to the complete observation case, the rates are reduced, due to incomplete information.

Construction of Virus-Free Switching Circuits
V. V. Tarasov
pp. 340–343

Abstract—We consider relay switching circuits constructed from switches whose operation is described by Boolean functions with external parameters ${z_1},\dots,{z_m}$ and a Boolean variable $x$ that controls the relay coil. We construct switching circuits that are free from the influence of external factors whose indicators are ${z_1},\dots,{z_m}$.

Self-averaging Property of Queuing Systems
A. A. Vladimirov, A. N. Rybko, and S. B. Shlosman
pp. 344–355

Abstract—We establish an averaging property for a one-server queuing process, $M(t)/G/1$. It is a new relation between the output flow rate and the input flow rate, crucial in the study of the Poisson hypothesis. Its implications include the statement that the output flow always possesses more regularity than the input flow.

On Flows in Simple Bidirected and Skew-Symmetric Networks
M. A. Babenko
pp. 356–370

Abstract—We consider a simple directed network. Results of Karzanov, Even, and Tarjan show that the blocking flow method constructs a maximum integer flow in this network in $O(m \min(m^{1/2}, n^{2/3}))$ time (hereinafter, $n$ denotes the number of nodes, and $m$ the number of arcs or edges). For the bidirected case, Gabow proposed a reduction to solve the maximum integer flow problem in $O(m^{3/2})$ time. We show that, with a variant of the blocking flow method, this problem can also be solved in $O(mn^{2/3})$ time. Hence, the gap between the complexities of directed and bidirected cases is eliminated. Our results are described in the equivalent terms of skew-symmetric networks. To obtain the time bound of $O(mn^{2/3})$, we prove that the value of an integer $s$–$s'$ flow in a skew-symmetric network without parallel arcs does not exceed $O(U n^2/d^2)$, where $d$ is the length of the shortest regular $s$–$s'$ path in the split network and $U$ is the maximum arc capacity. We also show that any acyclic integer flow of value $v$ in a skew-symmetric network without parallel arcs can be positive on at most $O(n \sqrt{v})$ arcs.

Invariance of the Stationary Distribution of States of Multimode Service Policy Networks
A. N. Starovoitov
pp. 371–378

Abstract—We consider open and closed preemptive-resume queueing systems with absolute priority of incoming customers. Single-server nodes have several service modes (regimes); the time of switching between the modes is exponential. Switching can be made to adjacent modes only. The amount of work required for servicing an incoming customer (workload) is a random variable with an arbitrary distribution function. For an open network, the input flow is Poissonian. We prove that the stationary distribution of the network states is invariant with respect to a functional form of workload distributions if the first moments are fixed.

Contemporary Debates on the Nature of Mathematics
A. N. Kolmogorov (Comments by V.A. Uspenskiy)
pp. 379–389

Abstract—Kolmogorov’s article “Contemporary Debates on the Nature of Mathematics” was published in 1929 in Nauchnoe slovo journal (no. 6, pp. 41–54) and has not been republished since then. At the end of the 19th and at the beginning of the 20th century, abstractions of a very high order appeared and were rooted in mathematics, so that their correlation with reality became a crucial question. A number of great mathematicians of the time were interested in this question, and Kolmogorov’s article was quite up to date. The goal of the republication of this article, which is currently difficult to access, is not only to acquaint the reader with a scarcely known article of the great scientist but to invite him to observe the process of scientific progress. It should be noted that, only a year after the publication of the article, some astonishing results of Gödel appeared that gave answers to a number of questions in Kolmogorov’s article and brought mathematical strictness in the very formulation of these questions. Therefore, the article is accompanied by external comments in order to give an insight into the current state of the art. In the text the comments are indicated by numbers in brackets, from [1] to [21]. As for the rest, Kolmogorov’s text is published in the same way as it was published in Nauchnoe slovo, without any alterations of the sense. Accompanying comments given to the article by the editors of Nauchnoe slovo (footnotes and introduction to the article) are omitted.

INDEX
pp. 390–393