### Course: A Crash Course on Coding Theory Lecturer: Madhu Sudan, MIT

#### Date: November 6 - 10, 2000 Location: IBM Almaden Research Center, San Jose, California

Organizers:
Presented under the auspices of the Special Focus on Computational Information Theory and Coding.

```This course is a fast-paced introduction to the theory of
error-correcting codes aimed at computer scientists. This theory,
dating back to the works of Shannon and Hamming from the late 40's,
overflows with theorems, techniques, and notions of interest to the
computer scientist. The course will focus on results of asymptotic or
algorithmic significance. The topics will be divided up as follows:

1. Introduction to the theory of error-correcting codes:
Describe motivation of error-correcting codes (ECCs) in the setting
of probabilistic noisy channels. Move to worst-case setting.
Introduce fundamental parameters: block length, information
rate, distance, and alphabet size. Introduce linear codes.

2. Construction and existence results for ECCs:
Basic ECCs: Hamming, Hadamard, Reed-Solomon, Reed-Muller, BCH.
Codes obtained by combining codes: tensor product and concatenation.
Example of Justesen codes.
Existence of good codes via the probabilistic method.
Bird's eyeview of Algebraic geometry (AG) codes.
(More codes to be introduced in Part 5.)

3. Limitations on the combinatorial performance of ECCs.
The nature of the tradeoff between rate and distance.
Quantitative review of positive results: (Justesen, Prob. codes, AG)
Limitation results: Singleton bound, Hamming bound, Plotkin
bound, and Bassalygo-Elias bounds.
(Perspective: How to deal with huge number of bounds?)
Duality and the MacWilliams Identities.
Linear Programming bound.

4. Decoding algorithms - Part 1.
The decoding problem: Unambigous and list-decoding versions.
Unambiguous Decoding for algebraic codes:
Example: Reed Solomon decoding
Abstracting to wide subfamily of linear codes.
Sample corollary: decoding AG codes.
List decoding for algebraic codes:
Example: Reed Solomon decoding
Abstracting to "ideal" codes.
Corollary: decoding number-theoretic codes.

5. Decoding algorithms - Part 2.
The linear time decoding problem: worst-case and random error settings.
Worst case setting: Expander (Spielman) codes.
Achieving Shannon limit on erasure channel.
(May include Turbo codes here).

6. Complexity results.
Complexity of the decoding problem for arbitrary linear codes.
Complexity of estimating the distance.
Decoding up to minimum distance.
Status of the ``decoding up to unambiguous decoding radius problem''

7. Applications in computer science. (Assorted collection.)

Breakup of topics to be covered:
Day 1 - Parts 1,2
Day 2 - Part 3
Day 3 - Part 4
Day 4 - Part 5
Day 5 - Parts 6, 7.
```

Next: Call for Participation
Workshop Index
DIMACS Homepage
Contacting the Center