Mary K. Wootters

Time- and Space-Efficient List Decoding up to Capacity

In the theory of error correcting codes, list-decoding refers to the following problem. Given a code $C \subseteq \Sigma^N$ and a received word $y \in \Sigma^N$, find all codewords $c \in C$ so that $\delta(c,y) \leq \rho$, where $\delta$ is relative Hamming distance and $\rho \in (0,1)$. Codes that approach the optima...