Document Summary:

This paper deals with complexity issues in the theory of linear error-correcting codes. Algorithmic problems that this paper study are constructing good codes, encoding and decoding them. According to their complexity, problems are divided into easy, i.e., polynomial in the length n of the code, and difficult, i.e., exponential ones. The first part deals with easy problems. This paper presents a construction of codes that correct a linear fraction of errors with complexity n log n. The construction is based on well-known since the late 80ies explicit constructions of good expanding graphs. Another group of problems in this part is related to codes for non-Hamming errors, namely, erasures, defects (codes for memories with defective cells), and localized errors.

The second part, which forms the core of this paper, deals with difficult problems, first and foremost, maximum likelihood decoding of linear codes. This paper studies separately the complexity of hard-decision and soft-decision decoding. For the hard-decision decoding case this paper presents algorithms grouped in two classes, gradient-like decoding and information-set decoding. It turns out that this general approach is sufficient to study most if not all known general decoding methods. In the soft-decision decoding context, this paper first discuss possible problem settings and then implementations of decoding with reduced complexity.

The last part of the paper overviews most known NP-hard decoding problems including some recent nonapproximability results.

The supporting material includes many general properties of linear codes from well-known to rather sophisticated, and a brief discussion of models of computations and relevant settings for the study of complexity issues in coding theory. This paper also gives examples of many methods studied. Sometimes they just illustrate concepts and definitions, but sometimes capture the most essential features of the proofs and on occasion even replace them.

Generally this paper gives complete and self-contained proofs of the results.

The coverage is extended from classical algorithms up to very recent developments. This paper thoroughly study and compare different algorithms, especially those applicable to several seemingly non-related problems. This unified approach to algorithmic coding problems enables us to organize previously independent results in a self-contained part of coding theory.