http://www.dagstuhl.de/11461

### November 13 – 18 , 2011, Dagstuhl Seminar 11461

# Coding Theory

## Organizers

Joachim Rosenthal (Universität Zürich, CH)

M. Amin Shokrollahi (EPFL – Lausanne, CH)

Judy L. Walker (University of Nebraska – Lincoln, US)

## For support, please contact

## Documents

Dagstuhl Report, Volume 1, Issue 11

List of Participants

Shared Documents

## Summary

This workshop brought together 42 researchers in key areas of coding theory. The seminar had a strong emphasis on interaction and collaboration among researchers. This goal was made clear in a series of five-minute talks by all seminar participants, where they briefly described their research interests and/or described a problem that they were currently working on. The rest of the time was dedicated to more in-depth talks by a selected number of researchers, but the lecture time was kept reasonably short so that long stretches of time were available for seminar participants who wished to discuss further and collaborate in small groups.

The talks fell into several broad categories, the most prominent of which was 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 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; this area began with a landmark paper by Sudan that proposed an algebraic list-decoding scheme for Reed-Solomon codes. List 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 embeds in the theory of Gröbner bases. There are emerging relationships between this area and codes on graphs, the leading question being whether 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.

Several talks covered recent advances and current research in some of the most notable questions that relate to algebraic constructions of codes, namely, list decoding; Berlekamp-Massey-like algorithms (for decoding, list-decoding, and Gröbner bases computation); elliptic curve methods and bent and hyperbent functions; rank-metric codes; bounds on codes (semidefinite programming bounds, BCH-like bounds); pivot distributions; properties of specific code constructions such as cyclic orbit codes, classes of self-dual codes, and codes obtained from generalized concatenation; and pseudocodewords, which straddle the boundary between algebraic analysis of codes and message-passing decoding of codes on graphs.

The second area that was covered in the workshop was that of codes on graphs. First proposed by Gallager in the 1950s, the subject of codes on graphs has experienced a huge revival over the past 10--15 years due to the fact that these codes have been shown to have capacity-achieving properties on some channels, and capacity-approaching properties on others. One of the most prominent examples in this area is that of the class of low density parity check (LDPC) codes, which are constructed from sparse bipartite graphs. The sparsity of the graph provides methods for construction of low complexity encoders and decoders. This area is a perfect nurturing ground for cross-fertilization of ideas between computer science, electrical engineering and mathematics. On the engineering side, the amazing simulation results have led some to declare the channel coding problem solved. The main proofs of asymptotic performance of these codes originated in the theoretical computer science community. Despite serious activities in this field many questions remain, related to the performance of graph-based codes and design of good LDPC codes. Several speakers discussed topics related to graph-based codes with applications beyond this field. The topics covered included design of sparse-graph codes for cooperation in communication networks; a new class of iterative decoders for LDPC codes; classes of tail-biting treillises; analysis of treillis pseudocodewords distributions; and bounds on the performance of quantum LDPC codes and their applications to percolations on graphs.

Network coding was another main area covered by the seminar. Network coding theory is concerned with the encoding and transmission of information where there may be many information sources and possibly many receivers. This is a very new area of coding theory and has been around only since 1999. The topic is somewhat far removed from the channel coding problem that Shannon proposed in 1948 and that the other areas of coding theory described in this proposal address. Indeed, there is not yet an agreed-upon formulation of the network coding problem. But there is a notion of linear network coding, and Li, Yeung and Cai showed in 2003 that it is possible to achieve so-called network capacity using linear codes alone. From that basis, much more algebra has been fruitfully introduced into the area. For example, in 2003, Kötter and Médard showed that the linear network codes that achieve a set throughput on a given network are precisely described by the points in a certain algebraic variety associated to the network. The Kötter-Médard approach, of course, relies on knowledge of the network in question. In practice, the network is typically unknown and often continually changing (dynamic). In 2008, Kötter and Kschischang considered random network coding and presented a framework in which the problem of network design is separated from that of code design. The idea is to assume that the network source simultaneously injects k linearly independent vectors from some vector space W into the network. These vectors are combined in various ways and sent through the network, so that the sink receives some linear combinations of them. The mathematical object that is invariant during transmission is the subspace of W spanned by the original k vectors, and so it is natural to consider a code in this context to be a subset of the set {P}(W) of all subspaces of W. Since {P}(W) is a metric space, the questions of code construction and optimality arise. Some approaches from classical coding theory can therefore be adopted in a fairly straight-forward manner, but deep questions remain, some of which were addressed by seminar speakers. One talk addressed the design and analysis of good end-to-end error-control codes in linear network coding; another topic was the analysis of several strategies for content distribution over network coded systems.

No workshop on such a practical topic as coding theory is complete without the mention of new and emerging applications. Indeed, several of the covered topics had a decidedly practical flavor, as some leading experts in applied coding theory, with an extensive mathematical background, reported about their work and provided insights into the directions the field will be taking in the coming years. Some of the most striking applications of coding-theoretical techniques to practical problems that were discussed included explicit constructions of regenerating codes for distributed storage; using network coding techniques to increase throughput in content distribution; and the design of iterative decoders for LDPC codes with better error floors than the traditional belief propagation decoders.

## Dagstuhl Seminar Series

- 16321: "Coding Theory in the Time of Big Data" (2016)
- 13351: "Coding Theory" (2013)

## Classification

- Algorithms And Complexity
- Networks
- Cryptography
- Algebraic Techniques

## Keywords

- Algebraic coding theory
- Complexity theory
- Cryptography
- Graph theory
- Graph based codes
- Information theory
- Randomized algorithms
- Networking
- Data distribution