List-decoding

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.

Mathematical formulation

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

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

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

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.

External links

* [http://theory.lcs.mit.edu/%7Emadhu/papers/ifip-journ.ps A Survey by Madhu Sudan on list decoding]
* [http://people.csail.mit.edu/madhu/FT01/ Notes from a course taught by Madhu Sudan]
* [http://www.cs.berkeley.edu/~luca/cs294/ Notes from a course taught by Luca Trevisan]