PROBLEMS OF INFORMATION TRANSMISSION

A translation of *Problemy Peredachi Informatsii*

Volume 57, Number 2, April–June, 2021

Back to contents page

**Minimax Theorems for Finite Blocklength Lossy
Joint Source-Channel Coding over an Arbitrarily Varying Channel
**

A. S. Vora and A. A. Kulkarni

pp. 99–128

**Abstract**—Motivated by applications in the security of cyber-physical
systems, we pose the finite blocklength communication problem in the presence of a
jammer as a zero-sum game between the encoder-decoder team and the jammer, by
allowing the communicating team as well as the jammer only locally randomized
strategies. The communicating team's problem is nonconvex under locally randomized
codes, and hence, in general, a minimax theorem need not hold for this game. However,
we show that *approximate minimax* theorems hold in the sense that the minimax
and maximin values of the game approach each other asymptotically. In particular, for
rates strictly below a critical threshold, *both* the minimax and maximin values
approach zero, and for rates strictly above it, they both approach unity. We then
show a *second-order* minimax theorem, i.e., for rates exactly approaching the
threshold along a specific scaling, the minimax and maximin values approach the same
constant value, that is neither zero nor one. Critical to these results is our
derivation of finite blocklength bounds on the minimax and maximin values of the game
and our derivation of second-order dispersion-based bounds.

**Coding in a Z-Channel in Case of Many Errors
**

V. S. Lebedev and N. A. Polyanskii

pp. 129–135

**Abstract**—We prove that the maximum number of words in a code that
corrects a fraction of $1/4+\varepsilon$ of asymmetric errors in a Z-channel is
$\Theta(\varepsilon^{-3/2})$ as $\varepsilon\to 0$.

**Bounds on Borsuk Numbers in Distance Graphs of a
Special Type
**

A. V. Berdnikov and A. M. Raigorodskii

pp. 136–142

**Abstract**—In 1933, Borsuk stated a conjecture, which has become
classical, that the minimum number of parts of smaller diameter into which an
arbitrary set of diameter 1 in $\mathbb{R}^n$ can be partitioned is $n+1$. In 1993,
this conjecture was disproved using sets of points with coordinates 0 and 1. Later,
the second author obtained stronger counterexamples based on families of points with
coordinates $-1$, $0$, and $1$. We establish new lower bounds for Borsuk numbers in
families of this type.

**Counting the Number of Perfect Matchings, and
Generalized Decision Trees
**

M. N. Vyalyi

pp. 143–160

**Abstract**—We consider a generalization of the
Pólya–Kasteleyn approach to counting the number of perfect matchings in a
graph based on computing the symbolic Pfaffian of a directed adjacency matrix of the
graph. Complexity of algorithms based on this approach is related to the complexity
of the sign function of a perfect matching in generalized decision tree models. We
obtain lower bounds on the complexity of the sign of a perfect matching in terms of
the deterministic communication complexity of the XOR sign function of a matching.
These bounds demonstrate limitations of the symbolic Pfaffian method for both the
general case and the case of sparse graphs.

**Limit Theorems for the Maximal Path Weight in a
Directed Graph on the Line with Random Weights of Edges
**

T. Konstantopoulos, A. V. Logachov, A. A. Mogulskii, and S. G. Foss

pp. 161–177

**Abstract**—We consider an infinite directed graph with vertices numbered
by integers $\ldots,-2,-1,0,1,2,\ldots\strut$, where any pair of vertices $j<k$ is
connected by an edge $(j,k)$ that is directed from $j$ to $k$ and has a random weight
$v_{j,k}\in [-\infty,\infty)$. Here, $\{v_{j,k},\: j<k\}$ is a family of
independent and identically distributed random variables that take either finite
values (of any sign) or the value $-\infty$. A path in the graph is a sequence of
connected edges $(j_0,j_1),(j_1,j_2),\ldots,(j_{m-1},j_m)$ (where
$j_0<j_1<\ldots <j_m$), and its weight is the sum $\sum\limits_{s=1}^m
v_{j_{s-1},j_s}\ge -\infty$ of the weights of the edges. Let $w_{0,n}$ be the maximal
weight of all paths from $0$ to $n$. Assuming that $\operatorname{\mathbf
P}(v_{0,1}>0)>0$, that the conditional distribution of $\operatorname{\mathbf
P}(v_{0,1}\in\cdot\,\,|\, v_{0,1}>0)$ is nondegenerate, and that
$\operatorname{\mathbf E}\exp (Cv_{0,1})<\infty$ for some $C=\mathrm{const}>0$,
we study the asymptotic behavior of random sequence $w_{0,n}$ as $n\to\infty$. In the
domain of the normal and moderately large deviations we obtain a local limit theorem
when the distribution of random variables $v_{i,j}$ is arithmetic and an
integro-local limit theorem if this distribution is non-lattice.

**Separable Collusion-Secure Multimedia Codes
**

E. E. Egorova and G. A. Kabatiansky

pp. 178–198

**Abstract**—We review known results about codes that are able to protect
multimedia content from illegal redistribution by coalitions of malicious users.