PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On the Smallest Size of an Almost Complete Subset of a Conic in $\operatorname{PG}(2,q)$ and Extendability of Reed–Solomon Codes
D. Bartoli, A. A. Davydov, S. Marcugini, and F. Pambianco
pp. 101–115

Abstract—In the projective plane $\operatorname{PG}(2,q)$, a subset $\mathcal{S}$ of a conic $\mathcal{C}$ is said to be almost complete if it can be extended to a larger arc in $\operatorname{PG}(2,q)$ only by the points of $\mathcal{C}\setminus \mathcal{S}$ and by the nucleus of $\mathcal{C}$ when $q$ is even. We obtain new upper bounds on the smallest size $t(q)$ of an almost complete subset of a conic, in particular, $$ \begin{aligned} t(q)&<\sqrt{q(3\ln q+\ln\ln q +\ln3)}+\smash[b]{\sqrt{\frac{q}{3\ln q}}} +4\sim\sqrt{3q\ln q},\\ t(q)&<1.835\sqrt{q\ln q}. \end{aligned} $$ The new bounds are used to extend the set of pairs $(N,q)$ for which it is proved that every normal rational curve in the projective space $\operatorname{PG}(N,q)$ is a complete $(q+1)$-arc, or equivalently, that no $[q+1,N+1,q-N+1]_q$ generalized doubly-extended Reed–Solomon code can be extended to a $[q+2,N+1,q-N+2]_q$ maximum distance separable code.

Compositional Restricted Multiple Access Channel
E. E. Egorova and V. S. Potapova
pp. 116–123

Abstract—We introduce the notion of a $q$-ary $s$-compositional code and prove that the rate, $R$, of the best such code satisfies for large $s$ the asymptotic inequalities $$ (q-1) \frac{\log_q s}{4s}\lesssim R \lesssim 2(q-1) \frac{\log_q s}{4s}. $$

On Discrimination between Classes of Distribution Tails
I. V. Rodionov
pp. 124–138

Abstract—We propose a test to distinguish between two classes of distribution tails using only higher order statistics of a sample and prove its consistency. We do not assume the corresponding distribution functions to belong to any maximum domain of attraction.

Improved Frankl–Rödl Theorem and Some of Its Geometric Consequences
A. A. Sagdeev
pp. 139–164

Abstract—We substantially improve a presently known explicit exponentially growing lower bound on the chromatic number of a Euclidean space with forbidden equilateral triangle. Furthermore, we improve an exponentially growing lower bound on the chromatic number of distance graphs with large girth. These refinements are obtained by improving known upper bounds on the product of cardinalities of two families of homogeneous subsets with one forbidden cross-intersection.

Clique Numbers of Random Subgraphs of Some Distance Graphs
A. S. Gusev
pp. 165–175

Abstract—We consider a class of graphs $G(n,r,s)=(V (n, r),E(n,r,s))$ defined as follows: $$ \begin{gathered} V(n,r)=\{\boldsymbol{x}=(x_1, x_2,\ldots,x_n):\: x_i\in\{0,1\},\: x_1+x_2+\ldots+x_n=r\},\\ E(n,r,s)=\{\{\boldsymbol{x}, \boldsymbol{y}\}:\: (\boldsymbol{x},\boldsymbol{y})=s\}, \end{gathered} $$ where $(x,y)$ is the Euclidean scalar product. We study random subgraphs $\mathcal{G}(G(n,r,s),p)$ with edges independently chosen from the set $E(n,r,s)$ with probability $p$ each. We find nontrivial lower and upper bounds on the clique number of such graphs.

Maximum Remaining Service Time in Infinite-Server Queues
A. V. Lebedev
pp. 176–190

Abstract—We study the maximum remaining service time in infinite-server queues of type $M|G|\infty$ (at a given time and in a stationary regime). The following cases for the arrival flow rate are considered: (1) time-independent, (2) given by a function of time, (3) given by a random process. As examples of service time distributions, we consider exponential, hyperexponential, Pareto, and uniform distributions. In the case of a constant rate, we study effects that arise when the average service time is infinite (for power-law distribution tails). We find the extremal index of the sequence of maximum remaining service times. The results are extended to queues of type $M^X|G|\infty$, including those with dependent service times within a batch.

Information-Theoretic Approach to Estimating the Capacity of Distributed Memory Systems
B. Ya. Ryabko
pp. 191–198

Abstract—Systems with cash memory (or more generally, with distributed memory) are very widely used in information technologies. Such are content delivery networks (CDN) of various types, which deliver digital movies, books, and similar content; peer-to-peer (P2P) networks, where millions of members exchange various information; and many other systems and devices of this kind. We introduce the notions of capacity and entropy efficiency for distributed memory systems, propose methods for estimating these quantities, and give an example of their application.