Autumn 2001, TTH 12:00-1:30
This course will focus on elements of the theory of
error-correcting codes and their applications to theoretical computer science.
The goals of modern coding theory are to construct explicit codes and establish bounds on their
information rate and distance, prove
lower bounds to explore the limits of achievable performance and devise efficient algorithms for
encoding and decoding specific codes. To achieve these goals, coding theory
draws upon combinatorics, probability, linear algebra, finite fields and
algebraic geometry. In recent years there has been a significant interplay
between coding theory, algorithms and computational complexity.
This course will cover the following four broad areas:
Constructions. Random linear codes, Hamming, Hadamard, Reed-Solomon, Reed-Muller
and Chinese Remainder Codes,
various concatenated codes.
Bounds. Packing bounds, Elias-Bassalygo and Johnson bounds, Fourier
theory for the discrete cube and the MacWiliams identities, linear programing
LP bound.
Algorithms. Decoding from erasures, unique decoding, list-decoding, expander
codes for linear-time encoding and decoding.
Applications. Hardcore predicates, reducing worst-case hardness to
average-case hardness, extractors and pseudo-random generators, other topics.
The main "text" will be:
and possibly some research papers. Background material can be
found in: