A list-decodable code with local encoding and decoding

Guruswamy and Indyk (2004) have shown that there exists an error-correcting code for which list-decoding from a (1-ε) fraction of errors can be done in linear time. We present a binary code for which list-decoding from a (1/2-ε) fraction of errors can be done in polylog time. The size of the list of candidates for the correct codeword is exponential but non-trivial and moreover is tight with respect to some known lower bounds. More precisely, for arbitrary constants ε>0 and λ>0 we present a code E : {0, 1}ⁿ → {0, 1}^n~ such that n^~ = n^O(log(1ε))/ and every ball in {0, 1}^n~ of radius ( 1/2 -ε)n^~ (in the Hamming-distance sense) contains at most 2^λn strings. Furthermore, the code E has encoding and list-decoding algorithms that produce each bit of their output in time polylog (n).