1. the use of codes to improve algorithmic efficiency
2. the theory of program testing and correcting, which is a complexity theoretic analogue of error detection and correction
3. the use of codes to obtain characterizations of traditional complexity classes such as NP and PSPACE; these new characterizations are in turn used to show that certain combinatorial optimization problems are as hard to approximate closely as they are to solve exactly.
This article is based on a talk given at the Short Course on Coding Theory at the American Mathematical Society meeting in San Francisco, CA in January, 1995.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-22.ps.gz
DIMACS Home Page