PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Conditions for Coincidence of the Classical Capacity and Entanglement-Assisted Capacity of a Quantum Channel
M. E. Shirokov
pp. 85–101

Abstract—Several relations between the Holevo capacity and entanglement-assisted classical capacity of a quantum channel are proved; necessary and sufficient conditions for their coincidence are obtained. In particular, it is shown that these capacities coincide if (respectively, only if) the channel (respectively, the $\chi$-essential part of the channel) belongs to the class of classical-quantum channels (the $\chi$-essential part is a restriction of a channel obtained by discarding all states that are useless for transmission of classical information). The obtained conditions and their corollaries are generalized to channels with linear constraints. By using these conditions it is shown that the question of coincidence of the Holevo capacity and entanglement-assisted classical capacity depends on the form of a constraint. Properties of the difference between quantum mutual information and the $\chi$-function of a quantum channel are explored.

Steiner Triple Systems $S(2^m-1,3,2)$ of Rank $2^m-m+1$ over $\mathbb{F}_2$
V. A. Zinoviev and D. V. Zinoviev
pp. 102–126

Abstract—Steiner systems $S(2^m-1,3,2)$ of rank $2^m - m+1$ over the field $\mathbb{F}_2$ are considered. A new recursive method for constructing Steiner triple systems of an arbitrary rank is proposed. The number of all Steiner systems of rank $2^m - m+1$ is obtained. Moreover, it is shown that all Steiner triple systems $S(2^m-1,3,2)$ of rank $r \le 2^m - m+1$ are derived, i.e., can be completed to Steiner quadruple systems $S(2^m,4,3)$. It is also proved that all such Steiner triple systems are Hamming; i.e., any Steiner triple system $S(2^m-1,3,2)$ of rank $r \le 2^m - m+1$ over the field $\mathbb{F}_2$ occurs as the set of words of weight $3$ of a binary nonlinear perfect code of length $2^m-1$.

On Frequency Estimation for a Periodic Ergodic Diffusion Process
R. Höpfner and Yu. A. Kutoyants
pp. 127–141

Abstract—We consider the problem of frequency estimation by observations for a periodic diffusion process possessing ergodic properties in two different situations. The first corresponds to a trend coefficient continuously differentiable with respect to parameter, and the second, to a discontinuous trend coefficient. It is shown that in the first case the maximum likelihood and Bayesian estimators are asymptotically normal with rate $T^{3/2}$, and in the second case these estimators have different limit distributions with rate $T^2$.

Sequential Estimation of a Threshold Crossing Time for a Gaussian Random Walk through Correlated Observations
M. V. Burnashev and A. Tchamkerten
pp. 142–153

Abstract—Given a Gaussian random walk $X$ with drift, we consider the problem of estimating its first-passage time $\tau_A$ for a given level $A$ from an observation process $Y$ correlated to $X$. Estimators may be any stopping times $\eta$ with respect to the observation process $Y$. Two cases of the process $Y$ are considered: a noisy version of $X$ and a process $X$ with delay $d$. For a given loss function $f(x)$, in both cases we find exact asymptotics of the minimal possible risk $\operatorname{\bf E} f((\eta-\tau_A)/r)$ as $A,d\to\infty$, where $r$ is a normalizing coefficient. The results are extended to the corresponding continuous-time setting where $X$ and $Y$ are Brownian motions with drift.

Toom’s Partial Order Is Transitive
M. A. Raskin
pp. 154–172

Abstract—We prove that the partial order on measures on biinfinite sequences proposed by Toom is transitive. This partial order was introduced as a possible tool for proving nonergodicity of some cellular automata.

Finding One of $D$ Defective Elements in Some Group Testing Models
R. Ahlswede^†, C. Deppe, and V. S. Lebedev
pp. 173–181

Abstract—In contrast to the classical goal of group testing, we consider the problem of finding $m$ defective elements out of $D$ ($m\le D$). We analyze two different test functions. We give adaptive strategies and present lower bounds for the number of tests and show that our strategy is optimal for $m=1$.

Proof of One Inequality in Identification Theory
V. M. Blinovsky
pp. 182–184

Abstract—We prove an inequality for the binary $L$-identification entropy which was conjectured in [1].

Geometric Relationship between Parallel Hyperplanes, Quadrics, and Vertices of a Hypercube
K. Yu. Gorbunov, A. V. Seliverstov, and V. A. Lyubetsky
pp. 185–192

Abstract—In a space of dimension 30 we find a pair of parallel hyperplanes, uniquely determined by vertices of a unit cube lying on them, such that strictly between the hyperplanes there are no vertices of the cube, though there are integer points. A similar two-sided example is constructed in dimension 37. We consider possible locations of empty quadrics with respect to vertices of the cube, which is a particular case of a discrete optimization problem for a quadratic polynomial on the set of vertices of the cube. We demonstrate existence of a large number of pairs of parallel hyperplanes such that each pair contains a large number of points of a prescribed set.

Reconstruction of Cyclic Words from Their Fragments
V. K. Leont'ev
pp. 193–197

Abstract—We consider the problem of reconstructing a cyclic word given a set of its fragments. We show that in the case where an unknown word is a cyclic shift of some fixed word with the number of ones in the latter coprime with the word length it suffices to have fragments of length 2.