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