List-decoding
From Wikipedia, the free encyclopedia
In computer science, particularly 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 1950's. 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.
[edit] Mathematical formulation
Let 
be a (n,k,d)q error-correcting code; in other words, is a code of length n, dimension k and minimum distance d over an alphabet Σ of size q. The list decoding problem can now be formulated as follows:
Input: Received word 
, error bound e
Output: A list of all codewords 
whose hamming distance from x is at most e.
[edit] Applications
Algorithms for list decoding of various codes have played a central role in a variety of results in complexity theory. Some important applications are construction of Hardcore Predicates from one-way permutations, amplifying hardness of boolean functions, construction of extractors.
