LINEAR PROGRAMMING BOUNDS ON CODES
Dr Ilia Krasikov, Department of Mathematical Sciences, Brunel University

Abstract: A code is a finite subset of a metric space. The minimal distance d of a code is the smallest distance between the codewords. One of the main problems in coding theory is to estimate the maximal possible d for a code of the given size (the number of codewords) |C|.

In this talk we briefly describe the most powerful presently known approach to this problem, the so called linear programming method. We discuss a variation of this technique based on the recently discovered phenomenon saying that, in a sense, any code looks similar to a random one. More precisely, let C be a binary code of length n. The spectrum of C is sequence B0, ..., Bn, where

\begin{displaymath}B_i \, = \, \frac{the \, number \, of \, the \, appearances \, of \, distance \, i} { the \, size\, of \, the \, code}\end{displaymath}

It turns out that in a certain interval of indices around n/2 the spectrum of any code is bounded by the spectrum of a random code of the same size and practically coincides with it somewhere on each short interval of indices. We explain how this idea can be applied to get better bounds for some families of codes.

This is joint work with Simon Litsyn from Tel-Aviv University.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 19 February 2001.

back