PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Strong Converse for the Feedback-Assisted Classical Capacity of Entanglement-Breaking Channels
D. Ding and M. M. Wilde
pp. 1–19

Abstract—Quantum entanglement can be used in a communication scheme to establish a correlation between successive channel inputs that is impossible by classical means. It is known that the classical capacity of quantum channels can be enhanced by such entangled encoding schemes, but this is not always the case. In this paper, we prove that a strong converse theorem holds for the classical capacity of an entanglement-breaking channel even when it is assisted by a classical feedback link from the receiver to the transmitter. In doing so, we identify a bound on the strong converse exponent, which determines the exponentially decaying rate at which the success probability tends to zero, for a sequence of codes with communication rate exceeding capacity. Proving a strong converse, along with an achievability theorem, shows that the classical capacity is a sharp boundary between reliable and unreliable communication regimes. One of the main tools in our proof is the sandwiched Rényi relative entropy. The same method of proof is used to derive an exponential bound on the success probability when communicating over an arbitrary quantum channel assisted by classical feedback, provided that the transmitter does not use entangled encoding schemes.

On the Energy-Constrained Diamond Norm and Its Application in Quantum Information Theory
M. E. Shirokov
pp. 20–33

Abstract—We consider a family of energy-constrained diamond norms on the set of Hermitian-preserving linear maps (superoperators) between Banach spaces of trace class operators. We prove that any norm from this family generates strong (pointwise) convergence on the set of all quantum channels (which is more adequate for describing variations of infinite-dimensional channels than the diamond norm topology). We obtain continuity bounds for information characteristics (in particular, classical capacities) of energy-constrained infinite-dimensional quantum channels (as functions of a channel) with respect to the energy-constrained diamond norms, which imply uniform continuity of these characteristics with respect to the strong convergence topology.

Mollard Code as a Robust Nonlinear Code
D. I. Kovalevskaya
pp. 34–47

Abstract—We consider the Mollard construction from the point of view of its efficiency for detecting multiple bit errors. We propose a generalization of the classical extended Mollard code to arbitrary code lengths. We show partial robustness of this construction: such codes have less undetected and miscorrected errors than linear codes. We prove that, for certain code parameters, the generalization of the Mollard construction can ensure better error protection than a generalization of Vasil'ev codes.

On Metric Dimension of Nonbinary Hamming Spaces
G. A. Kabatiansky and V. S. Lebedev
pp. 48–55

Abstract—For $q$-ary Hamming spaces we address the problem of the minimum number of points such that any point of the space is uniquely determined by its (Hamming) distances to them. It is conjectured that for a fixed $q$ and growing dimension $n$ of the Hamming space this number asymptotically behaves as $2n/\log_qn$. We prove this conjecture for $q=3$ and $q=4$; for $q=2$ its validity has been known for half a century.

General Independence Sets in Random Strongly Sparse Hypergraphs
A. S. Semenov and D. A. Shabanov
pp. 56–69

Abstract—We analyze the asymptotic behavior of the $j$-independence number of a random $k$-uniform hypergraph $H(n,k,p)$ in the binomial model. We prove that in the strongly sparse case, i.e., where $p=c\bigm/\dbinom{n-1}{k-1}$ for a positive constant $0\lt c\le 1/(k-1)$, there exists a constant $\gamma(k,j,c)\gt 0$ such that the $j$-independence number $\alpha_j(H(n,k,p))$ obeys the law of large numbers $$ \frac{\alpha_j(H(n,k,p))}{n}\xrightarrow{\bf P\,}\gamma(k,j,c)\quad \text{as}\ n\to+\infty. $$ Moreover, we explicitly present $\gamma(k,j,c)$ as a function of a solution of some transcendental equation.

Chromatic Numbers of Distance Graphs with Several Forbidden Distances and without Cliques of a Given Size
A. V. Berdnikov
pp. 70–83

Abstract—We consider distance graphs with $k$ forbidden distances in an $n$-dimensional space with the $p$-norm that do not contain cliques of a fixed size. Using a probabilistic construction, we present graphs of this kind with chromatic number at least $(Bk)^{Cn}$, where $B$ and $C$ are constants.

Gaussian Two-Armed Bandit and Optimization of Batch Data Processing
A. V. Kolnogorov
pp. 84–100

Abstract—We consider the minimax setting for the two-armed bandit problem with normally distributed incomes having a priori unknown mathematical expectations and variances. This setting naturally arises in optimization of batch data processing where two alternative processing methods are available with different a priori unknown efficiencies. During the control process, it is required to determine the most efficient method and ensure its predominant application. We use the main theorem of game theory to search for minimax strategy and minimax risk as Bayesian ones corresponding to the worst-case prior distribution. To find them, a recursive integro-difference equation is obtained. We show that batch data processing almost does not increase the minimax risk if the number of batches is large enough.