Local List-Decoding and Testing of Random Linear Codes from High Error

摘要

In this paper, we give surprisingly 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 (is contained in) {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~(-γ)), 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 had shown 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 significantly strengthen their results, while also having significantly 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 well known algorithms of Goldreich-Levin and Blum-Luby-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 super-constant 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-Wasserman and Feldman-Gopalan-Khot-Ponnuswami. 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.