Error-correcting codes and related combinatorial constructs
play an important role in several recent (and old) results
in computational complexity theory. In this paper we survey
results on locally-testable and locally-decodable error-correcting
codes, and their applications to complexity theory and to
cryptography.

Locally decodable codes are error-correcting codes with sub-linear
time error-correcting algorithms. They are related to private
information retrieval (a type of cryptographic protocol), and
they are used in average-case complexity and to construct
``hard-core predicates'' for one-way permutations. Locally
testable codes are error-correcting codes with sub-linear
time error-detection algorithms, and they are the combinatorial
core of probabilistically checkable proofs.