The complexity of error-correcting codes

Author: Daniel A. Spielman

Bibliographic Information: Invited lecture at the 11th International Symposium on Fundamentals of Computation Theory, Krakow, Poland, September 1997. Published in Lecture Notes in Computer Science #1279, pp. 67-84.


By concatenating linear-time codes with small, good codes, it is possible to construct in polynomial time a family of asymptotically good codes that approach the Shannon bound that can be encoded and decoded in linear time. Moreover, their probability of decoder error is exponentially small in the block length of the codes. In this survey, we will explain exactly what this statement means, how it is derived, and what problems in the complexity of error-correcting codes remain open. Along the way, we will survey some key developments in the complexity of error-correcting codes.
You can download this paper as Postscript, compressed Postscript, PDF, or compressed PDF.
Daniel A. Spielman
Last modified: Fri Aug 24 19:07:51 2001