Coding Theory

Abstract

The workshop on Coding Theory has brought together leading researchers in several key areas of mathematical coding theory. On the side of many mathematicians there were computer scientist and electrical engineers present. Participants came from many countries and the group included both senior and junior researchers.

Ever since its conception in the late 1940's, the theory of error-correcting codes has established itself as one of the central areas in mathematics.

Coding theory lies naturally at the intersection of a large number of disciplines in pure and applied mathematics: algebra and number theory, probability theory and statistics, communication theory, discrete mathematics and combinatorics, complexity theory, and statistical physics, are just but a few areas which have brought about very interesting applications in coding theory in recent years. The multitude of methods and means to construct and analyze codes and their properties suggests that a workshop with the explicit aim of bringing together researchers in different sub-fields of coding theory is necessary for cross-fertilization of ideas and global advancement of the field.

The following topics were covered during the workshop.

Combinatorial and probabilistic coding theory: This area has experienced a huge revival in recent years because of its success in the design of codes with superior performance. Very roughly, in this area combinatorial structures are used to construct error-correcting codes, and properties of these structures are used to design and analyze efficient encoding and decoding algorithms for the codes. One of the most prominent examples in this area is furnished by the class of LDPC codes. These codes are constructed from sparse bipartite graphs. More generally Michael Tanner showed in the 80's how to construct ‘general codes on graphs’.

The sparsity of the graph provides methods for construction of low complexity encoders and decoders. The graphs need to be designed in such a way as to facilitate an optimal operation of the algorithms. To achieve this goal researchers have developed and applied methods from probability theory and statistics, algebra, discrete mathematics, number theory, and statistical physics.

Algebraic coding theory: Algebraic coding theory primarily investigates codes obtained from algebraic constructions. Prime examples of this area of coding theory are codes from algebraic geometry, and codes obtained from algebraically constructed expander graphs. This discipline is almost as old as the coding theory itself, and has attracted (and continues to attract) some of the brightest minds in the field. Among the most exciting advances in this field in recent years has been the invention of list-decoding algorithms for various classes of algebraic codes. Such decoding algorithms yield for a received word a short list of codewords that have at most a given distance $\tau$ to the received word. The size of the list depends on the distance $\tau$. The methods in this field are mostly algebraic and make use of various properties of multivariate polynomials, or more generally, the properties of “well-behaved” functions in the function field of an irreducible variety. Methods from algebraic geometry are very important in this area. On the computational side the field naturally embedds in the theory of Gröbner bases. There are emerging relationships between this area and codes on graphs, the leading question being whether or not it is possible to match the superior performance of graph-based codes with list-decoding algorithms, or at least with algorithms that are derived from list-decoding algorithms.

Theoretical computer science: Theoretical computer science has cotributed a large number of ideas to coding theory. The above mentioned analysis and design of LDPC codes, and the conception of list-decoding algorithms are two prime examples of such contributions.

The reader will find it interesting to study in more details the summary of the talks collected in this report.