PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

The Sphere Packing Bound for Memoryless Channels
B. Nakiboğlu
pp. 201–244

Abstract—Sphere packing bounds (SPBs)—with prefactors that are polynomial in the block length—are derived for codes on two families of memoryless channels using Augustin's method: (possibly nonstationary) memoryless channels with (possibly multiple) additive cost constraints and stationary memoryless channels with convex constraints on the composition (i.e., empirical distribution, type) of the input codewords. A variant of Gallager's bound is derived in order to show that these sphere packing bounds are tight in terms of the exponential decay rate of the error probability with the block length under mild hypotheses.

Symmetric Block Designs and Optimal Equidistant Codes
L. A. Bassalygo, V. A. Zinoviev, and V. S. Lebedev
pp. 245–252

Abstract—We prove that any symmetric block design ($v,k,\lambda$) generates optimal ternary and quaternary constant-weight equidistant codes, whose parameters $n,N,w,d,q$ are uniquely determined by the parameters of the block design. For one rather special case, we construct symbolwise uniform equidistant codes of the minimum length.

On Geometric Goppa Codes from Elementary Abelian $p$-Extensions of $\mathbb{F}_{p^s}(x)$
N. Patanker and S. K. Singh
pp. 253–269

Abstract—Let $p$ be a prime number and $s>0$ an integer. In this short note, we investigate one-point geometric Goppa codes associated with an elementary abelian $p$-extension of $\mathbb{F}_{p^s}(x)$. We determine their dimension and exact minimum distance in a few cases. These codes are a special case of weak Castle codes. We also list exact values of the second generalized Hamming weight of these codes in a few cases. Simple criteria for self-duality and quasi-self-duality of these codes are also provided. Furthermore, we construct examples of quantum codes, convolutional codes, and locally recoverable codes on the function field.

Research on Fractional Critical Covered Graphs
S. Wang and W. Zhang
pp. 270–277

Abstract—A graph $G$ is called a fractional $(g,f)$-covered graph if for any $e\in E(G)$, $G$ admits a fractional $(g,f)$-factor covering $e$. A graph $G$ is called a fractional $(g,f,n)$-critical covered graph if for any $S\subseteq V(G)$ with $|S|=n$, $G-S$ is a fractional $(g,f)$-covered graph. A fractional $(g,f,n)$-critical covered graph is said to be a fractional $(a,b,n)$-critical covered graph if $g(x)=a$ and $f(x)=b$ for every $x\in V(G)$. A fractional $(a,b,n)$-critical covered graph was first defined and studied in [1]. In this article, we investigate fractional $(g,f,n)$-critical covered graphs and present a binding number condition for the existence of fractional $(g,f,n)$-critical covered graphs, which is an improvement and generalization of a previous result obtained in [2].

Gaussian Two-Armed Bandit: Limiting Description
A. V. Kolnogorov
pp. 278–301

Abstract—For a Gaussian two-armed bandit, which arises when batch data processing is analyzed, the minimax risk limiting behavior is investigated as the control horizon $N$ grows infinitely. The minimax risk is searched for as the Bayesian one computed with respect to the worst-case prior distribution. We show that the highest requirements are imposed on the control in the domain of “close” distributions where mathematical expectations of incomes differ by a quantity of the order of $N^{-1/2}$. In the domain of “close” distributions, we obtain a recursive integro-difference equation for finding the Bayesian risk with respect to the worst-case prior distribution, in invariant form with control horizon one, and also a second-order partial differential equation in the limiting case. The results allow us to estimate the performance of batch processing. For example, the minimax risk corresponding to batch processing of data partitioned into 50 batches can be only 2% greater than its limiting value when the number of batches grows infinitely. In the case of a Bernoulli two-armed bandit, we show that optimal one-by-one data processing is not more efficient than batch processing as $N$ grows infinitely.