PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On the BSC Reliability Function: Expanding the Region Where It Is Known Exactly
M. V. Burnashev
pp. 307–325

Abstract—We extend the “straight-line” region of transmission rates for which the BSC reliability function is known exactly.

Nonexistence of Binary Orthogonal Arrays via Their Distance Distributions
P. Boyvalenkov, H. Kulina, T. Marinova, and M. Stoyanova
pp. 326–334

Abstract—We investigate binary orthogonal arrays by making use of the fact that all possible distance distributions of the arrays under investigation and of related arrays can be computed. We apply certain relations for reducing the number of feasible distance distributions. In some cases this leads to nonexistence results. In particular, we prove that there exist no binary orthogonal arrays with parameters $(\text{strength},\text{length},\text{cardinality})=(4,10,6\cdot2^4)$, $(4,11,6\cdot2^4)$, $(4,12,7\cdot2^4)$, $(5,11,6\cdot2^5)$, $(5,12,6\cdot2^5)$, and $(5,13,7\cdot2^5)$.

Estimation of Matrices with Row Sparsity
O. Klopp and A. B. Tsybakov
pp. 335–348

Abstract—An increasing number of applications is concerned with recovering a sparse matrix from noisy observations. In this paper, we consider the setting where each row of an unknown matrix is sparse. We establish minimax optimal rates of convergence for estimating matrices with row sparsity. A major focus in the present paper is on the derivation of lower bounds.

On Regular Realizability Problems for Context-Free Languages
M. N. Vyalyi and A. A. Rubtsov
pp. 349–360

Abstract—We consider regular realizability problems, which consist in verifying whether the intersection of a regular language which is the problem input and a fixed language (filter) which is a parameter of the problem is nonempty. We study the algorithmic complexity of regular realizability problems for context-free filters. This characteristic is consistent with the rational dominance relation of CF languages. However, as we prove, it is more rough. We also give examples of both $\mathbf{P}$-complete and $\mathbf{NL}$-complete regular realizability problems for CF filters. Furthermore, we give an example of a subclass of CF languages for filters of which the regular realizability problems can have an intermediate complexity. These are languages with polynomially bounded rational indices.

The Laguerre-and-Sums-of-Powers Algorithm for the Efficient and Reliable Approximation of All Polynomial Roots
H. Möller
pp. 361–370

Abstract—We prove the first sufficient convergence criterion for Laguerre's root-finding algorithm, which by empirical evidence is highly efficient. The criterion is applicable to simple roots of polynomials with degree greater than 3. The “Sums of Powers Algorithm” (SPA), which is a reliable iterative root-finding method, can be used to fulfill the condition for each root. Therefore, Laguerre's method together with the SPA is now an efficient and reliable algorithm (LaSPA). In computational mathematics these results solve a central task which was first attacked by L. Euler 266 years ago.

A New Estimate for the Number of Edges in Induced Subgraphs of a Special Distance Graph
Ph. A. Pushnyakov
pp. 371–377

Abstract—We obtain new bounds for the number of edges in induced subgraphs of a special distance graph.

On One Method for Constructing a Family of Approximations of Zeta Constants by Rational Fractions
E. A. Karatsuba
pp. 378–390

Abstract—We present a new method for fast approximation of zeta constants, i.e., values $\zeta(n)$ of the Riemann zeta function, $n\ge 2$, $n$ is an integer, by rational fractions. The method makes it possible to fast approximate zeta constants and certain combinations of successive values of zeta constants by rational fractions. By choosing values of coefficients involved in the combinations, one can control the convergence rate of the approximations and the computation complexity for the zeta constants.

Interrelation of Families of Points of High Order on the Edwards Curve over a Prime Field
A. V. Bessalov and O. V. Tsygankova
pp. 391–397

Abstract—We propose a modification of the addition law on the Edwards curve over a prime field. We prove three theorems on properties of coordinates of high-order points and on a degenerate pair of twisted curves. We propose an algorithm for reconstructing all unknown points $kP$ of the Edwards curve when only $1/8$ of the points are known.

Analysis of Properties of $q$-ary Reed–Muller Error-Correcting Codes Viewed as Codes for Copyright Protection
V. M. Deundyak, S. A. Yevpak, and V. V. Mkrtichyan
pp. 398–408

Abstract—We consider a data protection scheme where error-correcting codes can be used for efficient protection against unauthorized copying organized by coalitions of cardinality $c\in\mathbb{N}$ of malicious users. We find limits of range of the parameters of prospective $q$-ary Reed–Muller codes for which these codes are $c$-TA and $c$-FP codes for copyright protection.