PROBLEMS OF INFORMATION TRANSMISSION

A translation of *Problemy Peredachi Informatsii*

Volume 54, Number 3, July–September, 2018

Back to contents page

** 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.