Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius

DOI10.1145/3357713.3384295MaRDI QIDQ5144940zbMATH OpenOpenAlexFDO

Authors Chong Shangguan, Itzhak Tamo

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.01502

zbMATH Keywords

generalized singleton boundJohnson radiuslist-decodingReed-Solomon codes

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Decoding (94B35) Bounds on codes (94B65)

Abstract: List-decoding of Reed-Solomon (RS) codes beyond the so called Johnson radius has been one of the main open questions since the work of Guruswami and Sudan. It is now known by the work of Rudra and Wootters, using techniques from high dimensional probability, that over large enough alphabets most RS codes are indeed list-decodable beyond this radius. In this paper we take a more combinatorial approach which allows us to determine the precise relation (up to the exact constant) between the decoding radius and the list size. We prove a generalized Singleton bound for a given list size, and conjecture that the bound is tight for most RS codes over large enough finite fields. We also show that the conjecture holds true for list sizes $2extand3$, and as a by product show that most RS codes with a rate of at least $1/9$ are list-decodable beyond the Johnson radius. Lastly, we give the first explicit construction of such RS codes. The main tools used in the proof are a new type of linear dependency between codewords of a code that are contained in a small Hamming ball, and the notion of cycle space from Graph Theory. Both of them have not been used before in the context of list-decoding.

Recommendations

• Improvements on the Johnson bound for Reed-Solomon codes
• Bounds on the List-Decoding Radius of Reed--Solomon Codes
• Combinatorial Limitations of Average-Radius List Decoding
• Every list-decodable code for high noise has abundant near-optimal rate puncturings
• Combinatorial bounds for list decoding

Cited in

(18)

• Improvements on the Johnson bound for Reed-Solomon codes
• Power decoding Reed-Solomon codes up to the Johnson radius
• Combinatorial Limitations of Average-Radius List Decoding
• The List Decoding Radius of Reed-Muller Codes over Small Fields
• Bounds on the List-Decoding Radius of Reed--Solomon Codes
• scientific article; zbMATH DE number 6850352 (Why is no real title available?)
• Every list-decodable code for high noise has abundant near-optimal rate puncturings
• Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes
• Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings
• Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Singleton-type bounds for list-decoding and list-recovery, and related results
• Random shortening of linear codes and applications
• Gabidulin codes achieve list decoding capacity with an order-optimal column-to-row ratio
• Pseudorandomness of expander walks via Fourier analysis on groups
• Near-optimal list-recovery of linear code families
• Random Reed-Solomon codes achieve the half-singleton bound for insertions and deletions over linear-sized alphabets
• List decoding of Reed-Solomon codes from a Gröbner basis perspective

This page was built for publication: Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144940)