PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Sharpening of an Upper Bound for the Reliability Function of a Binary Symmetric Channel
M. V. Burnashev
pp. 301–318

Abstract—An upper bound for the reliability function of a binary symmetric channel is improved.

Random Sphere Packing
V. M. Blinovsky
pp. 319–330

Abstract—We study probabilistic characteristics of random packings of a Euclidean space. The paper was initiated by [Shlosman, S. and Tsfasman, M., Moscow Math. J., 2001, vol. 1, no. 1, pp. 73–89], where typical properties of random lattices and random packings of a Euclidean space were studied. We use other (simpler and more precise) ways to obtain estimates on parameters that characterize random packings and consider the possibility of extending the results to $L$-packings.

On Cosets of Weight $4$ of Binary BCH Codes with Minimum Distance $8$ and Exponential Sums
V. A. Zinoviev, T. Helleseth, and P. Charpin
pp. 331–348

Abstract—We study coset weight distributions of binary primitive (narrow-sense) BCH codes of length $n=2^m$ ($m$ odd) with minimum distance $8$. In the previous paper [Charpin, P. and Zinoviev, V.A., SIAM J. Discrete Math., 1997, vol. 10, no. 1, pp. 128–145], we described coset weight distributions of such codes for cosets of weight $j=1,2,3,5,6$. Here we obtain exact expressions for the number of codewords of weight $4$ in terms of exponential sums of three types, in particular, cubic sums and Kloosterman sums. This allows us to find the coset distribution of binary primitive (narrow-sense) BCH codes with minimum distance $8$ and also to obtain some new results on Kloosterman sums over finite fields of characteristic $2$.

On DNA Codes
A. G. D'yachkov, P. A. Vilenkin, I. K. Ismagilov, R. S. Sarbaev, A. Macula, D. Torney, and S. White
pp. 349–367

Abstract—We develop and study the concept of similarity functions for $q$-ary sequences. For the case $q=4$, these functions can be used for a mathematical model of the DNA duplex energy [1: D'yachkov, A.G., Erdõs, P.L., Macula, A.J., Rykov, V.V., Torney, D.C., Tung, C.-S., Vilenkin, P.A., and White, P.S., J. Combin. Optimization, 2003, vol. 7, no. 4, pp. 369–379; 2: D'yachkov, A.G., Macula, A.J., Pogozelski, W.K., Renz, T.E., Rykov, V.V., and Torney, D.C., in Proc. 10th Int. Workshop on DNA Computing, Milan, Italy, 2004, pp. 90–103], which has a number of applications in molecular biology. Based on these similarity functions, we define a concept of DNA codes [1]. We give brief proofs for some of our unpublished results [D'yachkov, A.G., Torney, D.C., Vilenkin, P.A., and White, P.S., in Proc. 2002 IEEE Int. Symp. on Information Theory, Lausanne, Switzerland, 2002, pp. 372] connected with the well-known deletion similarity function [Levenshtein, V.I., Dokl. Akad. Nauk SSSR, 1965, vol. 163, no. 4, pp. 845–848 (Soviet Phys. Dokl. (Engl. Transl.), 1966, vol. 10, no. 8, pp. 707–710); 5: Levenshtein, V.I., in Diskretnaya matematika i matematicheskie voprosy kibernetiki (Discrete Mathematics and Mathematical Problems of Cybernetics), Moscow: Nauka, 1974, pp. 207–305; Levenshtein, V.I., J. Combin. Theory, Ser. A, 2001, vol. 93, no. 2, pp. 310–332]. This function is the length of the longest common subsequence; it is used in the theory of codes that correct insertions and deletions [5]. Principal results of the present paper concern another function, called the similarity of blocks. The difference between this function and the deletion similarity is that the common subsequences under consideration should satisfy an additional biologically motivated [2] block condition, so that not all common subsequences are admissible. We prove some lower bounds on the size of an optimal DNA code for the block similarity function. We also consider a construction of close-to-optimal DNA codes which are subcodes of the parity-check one-error-detecting code in the Hamming metric [MacWilliams, F.J. and Sloane, N.J.A., The Theory of Error-Correcting Codes, Amsterdam: North-Holland, 1977].

Recursive Aggregation of Estimators by the Mirror Descent Algorithm with Averaging
A. B. Juditsky, A. V. Nazin, A. B. Tsybakov, and N. Vayatis
pp. 368–384

Abstract—We consider a recursive algorithm to construct an aggregated estimator from a finite number of base decision rules in the classification problem. The estimator approximately minimizes a convex risk functional under the $\ell_1$-constraint. It is defined by a stochastic version of the mirror descent algorithm which performs descent of the gradient type in the dual space with an additional averaging. The main result of the paper is an upper bound for the expected accuracy of the proposed estimator. This bound is of the order $C\sqrt{(\log M)/t}$ with an explicit and small constant factor $C$, where $M$ is the dimension of the problem and $t$ stands for the sample size. A similar bound is proved for a more general setting, which covers, in particular, the regression model with squared loss.

A New Type of Attacks on Block Ciphers
B. Ya. Ryabko, V. A. Monarev, and Yu. I. Shokin
pp. 385–394

Abstract—A new attack (called “gradient statistical”) on block ciphers is suggested and experimentally investigated. We demonstrate the possibility of applying it to ciphers for which no attacks are known except for the exhaustive key search.