PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Plotkin Bound Generalization to the Case of Multiple Packings
V. M. Blinovsky
pp. 1–4

Abstract—We obtain an upper bound on the cardinality of a multiple packing in the case of a large decoding radius.

Central Limit Theorem and Large Deviations of the Fading Wyner Cellular Model via Product of Random Matrices Theory
N. Levy, O. Zeitouni, and S. Shamai (Shitz)
pp. 5–22

Abstract—We apply the theory of products of random matrices to the analysis of multi-user communication channels similar to the Wyner model, which are characterized by short-range intra-cell broadcasting. We study fluctuations of the per-cell sum-rate capacity in the non-ergodic regime and provide results of the type of the central limit theorem (CLT) and large deviations (LD). Our results show that CLT fluctuations of the per-cell sum-rate $C_m$ are of order $1/\sqrt{m}$, where $m$ is the number of cells, whereas they are of order $1/m$ in classical random matrix theory. We also show an LD regime of the form $\mathop{\bf P}(\lvert C_m-C\rvert>\varepsilon)\le e^{-m\alpha}$ with $\alpha=\alpha(\varepsilon)>0$ and $C=\smash[b]{\lim\limits_{m\to\infty}}C_m$, as opposed to the rate $e^{-m^2\alpha}$ in classical random matrix theory.

On Transitive Partitions of an $n$-Cube into Codes
F. I. Solov'eva
pp. 23–31

Abstract—We present methods to construct transitive partitions of the set $E^n$ of all binary vectors of length $n$ into codes. In particular, we show that for all $n=2^k-1$, $k\ge 3$, there exist transitive partitions of $E^n$ into perfect transitive codes of length $n$.

On the Construction of $(w,r)$ Cover-Free Codes
V. M. Sidelnikov^† and O. Yu. Prikhodov^†
pp. 32–36

Abstract—We construct a new class of concatenated cover-free codes. We prove that in this class there exists a sequence of $(w,r)$ cover-free codes which has a nonzero limit rate for $w,r=\operatorname{const}$. We consider application of cover-free codes to key distribution systems.

A Model of Restricted Asynchronous Multiple Access in the Presence of Errors
L. A. Bassalygo
pp. 37–45

Abstract—The paper is based on the brief communication [1], where proofs of results were omitted or drastically abridged. In the present paper, not only this gap is filled but also the very model of restricted asynchronous multiple access from [1] is considered in a somewhat more general situation.

Perceptrons of Large Weight
V. V. Podolskii
pp. 46–53

Abstract—A threshold gate is a linear combination of input variables with integer coefficients (weights). It outputs 1 if the sum is positive. The maximum absolute value of the coefficients of a threshold gate is called its weight. A degree-$d$ perceptron is a Boolean circuit of depth 2 with a threshold gate at the top and any Boolean elements of fan-in at most $d$ at the bottom level. The weight of a perceptron is the weight of its threshold gate.

For any constant $d\ge 2$ independent of the number of input variables $n$, we construct a degree-$d$ perceptron that requires weights of at least $n^{\Omega(n^d)}$; i.e., the weight of any degree-$d$ perceptron that computes the same Boolean function must be at least $n^{\Omega(n^d)}$. This bound is tight: any degree-$d$ perceptron is equivalent to a degree-$d$ perceptron of weight $n^{O(n^d)}$. For the case of threshold gates (i.e., $d=1$), the result was proved by Håstad in [2]; we use Håstad's technique.

Algorithmic Randomness and Splitting of Supermartingales
An. A. Muchnik^†
pp. 54–64

Abstract—Randomness in the sense of Martin-Löf can be defined in terms of lower semicomputable supermartingales. We show that such a supermartingale cannot be replaced by a pair of supermartingales that bet only on even bits (the first one) and on odd bits (the second one) knowing all the preceding bits.

On Decay of Correlations for an Exclusion Process with Asymmetric Boundary Conditions
V. A. Malyshev and V. A. Shvets
pp. 65–73

Abstract—We consider a symmetric exclusion process on a discrete interval of $S$ points with various boundary conditions at the endpoints. We study the asymptotic decay of correlations as $S\to\infty$. The main result is proving asymptotic independence of a stationary distribution at points of the interval that are far enough away. We do not use Derrida's algebraic technique but develop a new technique, which has a visual probabilistic sense.