A Fourier-Analytic Approach to List-Decoding for Sparse Random Linear Codes

Akinori KAWACHI; Ikko YAMANE

doi:10.1587/transinf.2014FCP0016

A Fourier-Analytic Approach to List-Decoding for Sparse Random Linear Codes

Akinori KAWACHI, Ikko YAMANE

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E98-D No.3 pp.532-540

Publication Date: 2015/03/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2014FCP0016

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science---New Spirits in Theory of Computation and Algorithm---)

Category

Authors

Akinori KAWACHI
Tokyo Institute of Technology
Ikko YAMANE
Tokyo Institute of Technology

Keyword

list-decoding, Fourier analysis

Cite this

Copy

Akinori KAWACHI, Ikko YAMANE, "A Fourier-Analytic Approach to List-Decoding for Sparse Random Linear Codes" in IEICE TRANSACTIONS on Information, vol. E98-D, no. 3, pp. 532-540, March 2015, doi: 10.1587/transinf.2014FCP0016.
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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2014FCP0016/_p

Copy

@ARTICLE{e98-d_3_532,
author={Akinori KAWACHI, Ikko YAMANE, },
journal={IEICE TRANSACTIONS on Information},
title={A Fourier-Analytic Approach to List-Decoding for Sparse Random Linear Codes},
year={2015},
volume={E98-D},
number={3},
pages={532-540},
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.},
keywords={},
doi={10.1587/transinf.2014FCP0016},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - A Fourier-Analytic Approach to List-Decoding for Sparse Random Linear Codes
T2 - IEICE TRANSACTIONS on Information
SP - 532
EP - 540
AU - Akinori KAWACHI
AU - Ikko YAMANE
PY - 2015
DO - 10.1587/transinf.2014FCP0016
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2015
AB - 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.
ER -