Paper Info
Title
Local list-decoding and testing of random linear codes from high error
Abstract
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 ⊆ 0,1N which is: sparse: |C| ≤ Nc, and unbiased: each nonzero codeword in C has weight in (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 non-trivial 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.
Year
DOI
Venue
2010
10.1145/1806689.1806748
SIAM Journal on Computing
Keywords
Field
DocType
self-correcting operation,property testing,sublinear-time algorithms,unbiased code,subexponential time algorithm,constant number,list-decoding,random linear code,high-error regime,inverse-polynomial rate,dual-bch codes,high error,noisy parity,constant fraction,random codes,local list-decoding,linear code,word w,bch code,list decoding
Discrete mathematics,Locally decodable code,Concatenated error correction code,Combinatorics,Low-density parity-check code,Block code,Reed–Muller code,Code word,Linear code,Prefix code,Mathematics
Conference
ISSN
Citations 
PageRank 
0737-8017
7
0.47
References 
Authors
24
2
Name
Order
Citations
PageRank
Swastik Kopparty138432.89
Shubhangi Saraf226324.55