Error-Correcting Codes in Complexity Theory

A series of two lectures  to be given in Rome, Italy, May 27, 2003.
Error-correcting codes and related combinatorial constructs play an important role is several recent (and old) results in complexity theory. This course will give a brief overview of the theory, constructions, algorithms, and applications of error-correcting codes.

We will start with the basic definitions and the constructions of Reed-Solomon, and low-weight parity-check codes, then see unique-decoding and, possibly,  list-decoding algorithms. Finally, as time allows, we will look at applications in complexity theory.

Suggested readings