In coding theory, list decoding is an alternative to unique decoding of error-correcting codes for large error rates. The notion was proposed by Elias in the 1950s. The main idea behind list decoding is that the decoding algorithm instead of outputting a single possible message outputs a list of possibilities one of which is correct. This allows for handling a greater number of errors than that allowed by unique decoding.

The unique decoding model in coding theory, which is constrained to output a single valid codeword from the received word could not tolerate a greater fraction of errors. This resulted in a gap between the error-correction performance for stochastic noise models (proposed by Shannon) and the adversarial noise model (considered by Richard Hamming). Since the mid 90s, significant algorithmic progress by the coding theory community has bridged this gap. Much of this progress is based on a relaxed error-correction model called list decoding, wherein the decoder outputs a list of codewords for worst-case pathological error patterns where the actual transmitted codeword is included in the output list. In case of typical error patterns though, the decoder outputs a unique single codeword, given a received word, which is almost always the case (However, this is not known to be true for all codes). The improvement here is significant in that the error-correction performance doubles. This is because now the decoder is not confined by the half-the-minimum distance barrier. This model is very appealing because having a list of codewords is certainly better than just giving up. The notion of list-decoding has many interesting applications in complexity theory.

The way the channel noise is modeled plays a crucial role in that it governs the rate at which reliable communication is possible. There are two main schools of thought in modeling the channel behavior:

The highlight of list-decoding is that even under adversarial noise conditions, it is possible to achieve the information-theoretic optimal trade-off between rate and fraction of errors that can be corrected. Hence, in a sense this is like improving the error-correction performance to that possible in case of a weaker, stochastic noise model.

Let ${\displaystyle {\mathcal {C}}}$ be a ${\displaystyle (n,k,d)_{q}}$ error-correcting code; in other words, ${\displaystyle {\mathcal {C}}}$ is a code of length ${\displaystyle n}$, dimension ${\displaystyle k}$ and minimum distance ${\displaystyle d}$ over an alphabet ${\displaystyle \Sigma }$ of size ${\displaystyle q}$. The list-decoding problem can now be formulated as follows:

Input: Received word ${\displaystyle x\in \Sigma ^{n}}$, error bound ${\displaystyle e}$

Output: A list of all codewords ${\displaystyle x_{1},x_{2},\ldots ,x_{m}\in {\mathcal {C}}}$ whose hamming distance from ${\displaystyle x}$ is at most ${\displaystyle e}$.

Given a received word ${\displaystyle y}$, which is a noisy version of some transmitted codeword ${\displaystyle c}$, the decoder tries to output the transmitted codeword by placing its bet on a codeword that is “nearest” to the received word. The Hamming distance between two codewords is used as a metric in finding the nearest codeword, given the received word by the decoder. If ${\displaystyle d}$ is the minimum Hamming distance of a code ${\displaystyle {\mathcal {C}}}$, then there exists two codewords ${\displaystyle c_{1}}$ and ${\displaystyle c_{2}}$ that differ in exactly ${\displaystyle d}$ positions. Now, in the case where the received word ${\displaystyle y}$ is equidistant from the codewords ${\displaystyle c_{1}}$ and ${\displaystyle c_{2}}$, unambiguous decoding becomes impossible as the decoder cannot decide which one of ${\displaystyle c_{1}}$ and ${\displaystyle c_{2}}$ to output as the original transmitted codeword. As a result, the half-the minimum distance acts as a combinatorial barrier beyond which unambiguous error-correction is impossible, if we only insist on unique decoding. However, received words such as ${\displaystyle y}$ considered above occur only in the worst-case and if one looks at the way Hamming balls are packed in high-dimensional space, even for error patterns ${\displaystyle e}$ beyond half-the minimum distance, there is only a single codeword ${\displaystyle c}$ within Hamming distance ${\displaystyle e}$ from the received word. This claim has been shown to hold with high probability for a random code picked from a natural ensemble and more so for the case of Reed–Solomon codes which is well studied and quite ubiquitous in the real world applications. In fact, Shannon's proof of the capacity theorem for q-ary symmetric channels can be viewed in light of the above claim for random codes.