Local list-decoding and testing of random linear codes from high error

摘要

In this paper, we give efficient algorithms for list-decoding and testing random linear codes. Our main result is that random sparse linear codes are locally list-decodable and locally testable in the high-error regime with only a constant number of queries. More precisely, we show that for all constants c > 0 and γ > 0, and for every linear code C ? {0, 1}~N which is (1) sparse: |C| ≤ N~c, and (2) unbiased: each nonzero codeword in C has weight ε(1/2 -N~(-γ), 1/2 + N ~(-γ)), then C is locally testable and locally list-decodable from (1/2 -ε)-fraction worst-case errors using only poly(1 ε) queries to a received word. We also give subexponential time algorithms for list-decoding arbitrary unbiased (but not necessarily sparse) linear codes in the high-error regime. In particular, this yields the first subexponential time algorithm even for the problem of (unique) decoding random linear codes of inverse-polynomial rate from a fixed positive fraction of errors. Earlier, Kaufman and Sudan showed that sparse, unbiased codes can be locally (unique) decoded and locally tested from a constant fraction of errors, where this constant fraction tends to 0 as the number of codewords grows. Our results strengthen their results, while also having simpler proofs. At the heart of our algorithms is a natural "self-correcting" operation defined on codes and received words. This self-correcting operation transforms a code C with a received word w into a simpler code C and a related received word w′ such that w is close to C if and only if w′ is close to C′. Starting with a sparse, unbiased code C and an arbitrary received word w, a constant number of applications of the self-correcting operation reduces us to the case of local list-decoding and testing for the Hadamard code, for which the wellknown algorithms of Goldreich and Levin and Blum, Luby, and Rubinfeld are available. This yields the constant-query local algorithms for the original code C. Our algorithm for decoding unbiased linear codes in subexponential time proceeds similarly. Applying the self-correcting operation to an unbiased code C and an arbitrary received word a superconstant number of times, we get reduced to the problem of learning noisy parities, for which nontrivial subexponential time algorithms were recently given by Blum, Kalai, and Wasserman and Feldman et al. Our result generalizes a result of Lyubashevsky, which gave a subexponential time algorithm for decoding random linear codes of inverse-polynomial rate from random errors.