Time- and Space-Efficient List Decoding up to Capacity

Dorsa Fathollahi, Noga Ron-Zewi, Mary Wootters

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$…