List decoding

List decoding is a generalization of standard decoding for error-correcting codes in which the decoder is allowed to output a small list of candidate messages rather than a single answer. When a codeword is corrupted beyond the unique decoding radius — the point where standard decoding fails because multiple codewords are equally close — list decoding can still recover the correct message by returning all plausible candidates. The paradigm shift is from uniqueness to small-set recovery.

List decoding was introduced by Elias and Wozencraft in the 1950s, but its power was fully realized only in the 1990s when Sudan, Guruswami, and others showed that certain codes can be list-decoded up to their information-theoretic capacity. The technique is now central to hardness amplification: the list-decoding property of a code is what makes it possible to extract a small circuit from a solver that is only partially correct, turning weak hardness into strong hardness.