PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Gaussian Classical-Quantum Channels: Gain from Entanglement-Assistance
A. S. Holevo
pp. 1–14

Abstract—In the present paper we introduce and study Bosonic Gaussian classical-quantum (c-q) channels; embedding of the classical input in quantum input is always possible, and therefore the classical entanglement-assisted capacity $C_{\rm ea}$ under an appropriate input constraint is well defined. We prove the general property of entropy increase for a weak complementary channel, which implies the equality $C=C_{\rm ea}$ (where $C$ is the unassisted capacity) for a certain class of c-q Gaussian channels under an appropriate energy-type constraint. On the other hand, we show by an explicit example that the inequality $C< C_{\rm ea}$ is not unusual for constrained c-q Gaussian channel.

On the Weakest Resource for Coordination in Arbitrarily Varying Multiple Access Channels with Conferencing Encoders
M. Wiese and H. Boche
pp. 15–26

Abstract—If senders and a receiver of an arbitrarily varying multiple-access channel (AV-MAC) have access to outputs of discrete correlated memoryless sources, the same rate region is achievable as if common randomness were available, no matter how small the correlation is. This reduces the necessary amount of cooperation in an AV-MAC considerably. Moreover, to transmit blocklength-$n$ words, no more than order $\log n$ source outputs are required.

Bounds on the Rate of Disjunctive Codes
A. G. D'yachkov, I. V. Vorob'ev, N. A. Polyansky, and V. Yu. Shchukin
pp. 27–56

Abstract—A binary code is said to be a disjunctive $(s,\ell)$ cover-free code if it is an incidence matrix of a family of sets where the intersection of any $\ell$ sets is not covered by the union of any other $s$ sets of this family. A binary code is said to be a list-decoding disjunctive of strength $s$ with list size $L$ if it is an incidence matrix of a family of sets where the union of any $s$ sets can cover no more that $L-1$ other sets of this family. For $L=\ell=1$, both definitions coincide, and the corresponding binary code is called a disjunctive $s$-code. This paper is aimed at improving previously known and obtaining new bounds on the rate of these codes. The most interesting of the new results is a lower bound on the rate of disjunctive $(s,\ell)$ cover-free codes obtained by random coding over the ensemble of binary constant-weight codes; its ratio to the best known upper bound converges as $s\to\infty$, with an arbitrary fixed $\ell\ge1$, to the limit $2e^{-2}=0.271\ldots$. In the classical case of $\ell=1$, this means that the upper bound on the rate of disjunctive $s$-codes constructed in 1982 by D'yachkov and Rykov is asymptotically attained up to a constant factor $a$, $2e^{-2}\le a\le1$.

Zero-One Law for Random Distance Graphs with Vertices in $\{-1,0,1\}^n$
S. N. Popova
pp. 57–78

Abstract—We study zero-one laws for random distance graph with vertices in $\{-1, 0, 1\}^n$ depending on a set of parameters. We give some conditions under which sequences of random distance graphs obey or do not obey the zero-one law.

On the Rank of Incidence Matrices for Points and Lines of Finite Affine and Projective Geometries over a Field of Four Elements
M. E. Kovalenko and T. A. Urbanovich
pp. 79–89

Abstract—We consider incidence matrices for points and lines of affine and projective geometries over a field of four elements. For such matrices we derive a simple formula for the 2-rank and, as a consequence, new combinatorial identities expressing the relation of the obtained formulas for the rank with previously known formulas. We also present a way to construct generating systems for rows of these matrices.

Distribution of $r$-Tuples in One Class of Uniformly Distributed Sequences over Residue Rings
O. V. Kamlovskii
pp. 90–105

Abstract—We consider the distribution of $r$-tuples in one class of uniformly distributed linear recurring sequences over residue rings. We establish bounds for the number of occurrences of a given $r$-tuple and prove that these bounds are asymptotically the best possible.

Conditions for a Product-Form Stationary Distribution of One Queueing System with Batch Transfers and a Disaster Flow
A. N. Starovoitov
pp. 106–116

Abstract—We consider an open exponential network with two types of arrival flows at the network nodes: a message flow and a disaster flow. Messages arriving at the nodes form batches of customers of a random size. A disaster arrival at a node completely empties the queue at the node if it is nonempty and has no effect otherwise. Customers are served in batches of a random size. After a batch is served at a node, the batch quits the network and, according to a routing matrix, either sends a message or a disaster to another node or does not send anything. We find conditions for the stationary distribution of the network state probabilities to be represented as a product of shifted geometric distributions.