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

• KAWACHI Akinori

  Tokyo Institute of Technology

• YAMANE Ikko

  Tokyo Institute of Technology

抄録

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.

収録刊行物

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E98.D (3), 532-540, 2015

  一般社団法人 電子情報通信学会

キーワード

• list-decoding
• Fourier analysis

詳細情報

• CRID: 1390001204380065280
• NII論文ID: 130004841870
• DOI: 10.1587/transinf.2014fcp0016
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E98.D/3/E98.D_2014FCP0016/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可