A translation of Problemy Peredachi Informatsii

Volume 54, Number 3, July–September, 2018
Back to contents page

CONTENTS                   Powered by MathJax


Analytical Properties of Shannon's Capacity of Arbitrarily Varying Channels under List Decoding: Super-Additivity and Discontinuity Behavior
H. Boche, R. F. Schaefer, and H. V. Poor
pp. 199–228

Abstract—The common wisdom is that the capacity of parallel channels is usually additive. This was also conjectured by Shannon for the zero-error capacity function, which was later disproved by constructing explicit counterexamples demonstrating the zero-error capacity to be super-additive. Despite these explicit examples for the zero-error capacity, there is surprisingly little known for nontrivial channels. This paper addresses this question for the arbitrarily varying channel (AVC) under list decoding by developing a complete theory. The list capacity function is studied and shown to be discontinuous, and the corresponding discontinuity points are characterized for all possible list sizes. For parallel AVCs it is then shown that the list capacity is super-additive, implying that joint encoding and decoding for two parallel AVCs can yield a larger list capacity than independent processing of both channels. This discrepancy is shown to be arbitrarily large. Furthermore, the developed theory is applied to the arbitrarily varying wiretap channel to address the scenario of secure communication over AVCs.


On Some Optimization Problems for the Rényi Divergence
V. V. Prelov
pp. 229–244

Abstract—We consider the problem of determining the maximum and minimum of the Rényi divergence $D_{\lambda}(P\,||\,Q)$ and $D_{\lambda}(Q\,||\,P)$ for two probability distribution $P$ and $Q$ of discrete random variables $X$ and $Y$ provided that the probability distribution $P$ and the parameter $\alpha$ of $\alpha$-coupling between $X$ and $Y$ are fixed, i.e., provided that $\Pr\{X=Y\}=\alpha$.


On $m$-Near-Resolvable Block Designs and $q$-ary Constant-Weight Codes
L. A. Bassalygo, V. A. Zinoviev, and V. S. Lebedev
pp. 245–252

Abstract—We introduce $m$-near-resolvable block designs. We establish a correspondence between such block designs and a subclass of (optimal equidistant) $q$-ary constant-weight codes meeting the Johnson bound. We present constructions of $m$-near-resolvable block designs, in particular based on Steiner systems and super-simple $t$-designs.


New Good's Type Kronecker Power Expansions
M. S. Bespalov
pp. 253–257

Abstract—We propose a new version of the proof of Good's theorem stating that the Kronecker power of an arbitrary square matrix can be represented as a matrix power of a sparse matrix $Z$. We propose new variants of sparse matrices $Z$. We observe that for another version of the tensor power of a matrix, the $b$-power, there exists an analog of another Good's expansion but no analog of this theorem.


On the Complexity of Polynomial Recurrence Sequences
S. S. Marchenkov
pp. 258–262

Abstract—We consider recurrence sequences over the set of integers with generating functions being arbitrary superpositions of polynomial functions and the $\operatorname{sg}$ function, called polynomial recurrence sequences. We define polynomial-register (PR) machines, close to random-access machines. We prove that computations on PR machines can be modeled by polynomial recurrence sequences. On the other hand, computation of elements of a polynomial recurrence sequence can be implemented using a suitable PR machine.


A Local Large Deviation Principle for Inhomogeneous Birth–Death Processes
N. D. Vvedenskaya, A. V. Logachov, Yu. M. Suhov, and A. A. Yambartsev
pp. 263–280

Abstract—The paper considers a continuous-time birth–death process where the jump rate has an asymptotically polynomial dependence on the process position. We obtain a rough exponential asymptotic for the probability of trajectories of a re-scaled process contained within a neighborhood of a given continuous nonnegative function.


Infinite Spectra of First-Order Properties for Random Hypergraphs
S. N. Popova
pp. 281–289

Abstract—We study the asymptotic behavior of probabilities of first-order properties for random uniform hypergraphs. In 1990, J. Spencer introduced the notion of a spectrum for graph properties and proved the existence of a first-order property with an infinite spectrum. In this paper we give a definition of a spectrum for properties of uniform hypergraphs and establish an almost tight bound for the minimum quantifier depth of a first-order formula with infinite spectrum.


Propagation of Chaos and Poisson Hypothesis
A. A. Vladimirov, S. A. Pirogov, A. N. Rybko, and S. B. Shlosman
pp. 290–299

Abstract—We establish the strong Poisson hypothesis for symmetric closed networks. In particular, we prove asymptotic independence of nodes as the size of the system tends to infinity.