Abstract | ||
---|---|---|
It is widely known that decoding problems for random linear codes are computationally hard in general. Surprisingly, Kopparty and Saraf proved query-efficient list-decodability of sparse random linear codes by showing a reduction from a decoding problem for sparse random linear codes to that for the Hadamard code with small number of queries even under high error rate [11]. In this paper, we show a more direct list-decoding algorithm for sparse random linear codes with small number of queries from a Fourier-analytic approach. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1587/transinf.2014FCP0016 | IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS |
Keywords | Field | DocType |
list-decoding, Fourier analysis | Sequential decoding,Berlekamp–Welch algorithm,Fourier analysis,Computer science,Sparse approximation,Fourier transform,Theoretical computer science,Linear code,List decoding | Journal |
Volume | Issue | ISSN |
E98D | 3 | 1745-1361 |
Citations | PageRank | References |
1 | 0.35 | 6 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Akinori Kawachi | 1 | 185 | 20.66 |
Ikko Yamane | 2 | 1 | 0.35 |