Oberwolfach-Seminar: The Mathematics of Error-Correcting Codes

October 15th - October 21st, 2006
Henry Cohn, Microsoft Research
Nati Linial, Jerusalem
Madhu Sudan, MIT Cambridge
Alex Samorodnitsky, Jerusalem
Background and Programme:
Shannon's ground-breaking work in which Information Theory was born is generally considered one of the greatest scientific achievements of the 20th century. This theory comes hand in hand with the Theory of Communication and the problems one faces in attempting to communicate reliably over noisy communication channels. The study of such problems has evolved into the field of Error-Correcting Codes . In the most basic scenario one transmits n-bit long messages. However, in order to deal with noise that may arise during transmission, some efficiency must be given up. From among all 2n possible n-bit strings we consider only a subset C ⊆ {0,1}n ("a code book") and restrict all our messages to n-bit strings from C. In this theory a subset C ⊆ {0,1}n is called a code (or a binary code when we want to stress that our alphabet is the set {0,1}n.) Consider a message y ∈ {0,1}n that reaches the receiver. The simplest situation is when y ∈ C, in which case we assume that the message y is indeed what the transmitter had sent. If, however, y ∉ C, we assume that y is a noisy version of some x ∈ C. We pick that x ∈ C that is the most likely original message, namely, the one that differs from y in the smallest possible number of bits, i.e., that x ∈ C which minimizes dH(x,y). Here dH(u,v) is the Hamming distance between the two strings u, v ∈ {0,1}n, namely, the number of coordinates in which they differ dH(u,v)=|{i | ui ≠ vi}|. It follows that if every two distinct members u, v ∈ C are at distance dH(u,v) ≥ r, then our conclusion is correct whenever no more than ⌊r/2⌋ errors occur. In this case we say that the code C ⊆ {0,1}n is ⌊r/2⌋-error-correcting .

Thus we understand that a major issue in the theory is to find codes which meet two inherently conflicting goals

Understanding this tradeoffs is a mystery that has baffled mathematicians for many years. This fundamental problem is one of the main focal points of this school. A main specific challenge is to understand how large R(C) can be if C ⊂ {0,1}n satisfies δ(C) ≥ x for some 1 ≥ x ≥ 0 and n is large. This maximum is usually denoted by R(x).

New developments:
We intend to mention some fascinating new developments in the mathematical aspects of coding theory. Here are some of the possible topics.
Deadline for applications:
September 1, 2006

The seminars take place at the Mathematisches Forschungsinstitut Oberwolfach. The number of participants is restricted to 24. The Institute covers accommodation and food. Travel expenses cannot be reimbursed. Applications including

should be sent as hard copy or by e-mail (.ps or .pdf file) to:

Prof. Dr. Gert-Martin Greuel
Universität Kaiserslautern
Fachbereich Mathematik
Erwin Schrödingerstr.
67663 Kaiserslautern, Germany

Mathematisches Forschungsinstitut Oberwolfach   updated: May 16, 2006