List decodability of Reed-Solomon codes up to capacity
List decodability of Reed-Solomon codes up to capacity
Let be a finite field and let be an evaluation set. For rate , write for the corresponding Reed-Solomon code, and let denote the maximum, over received words, of the number of codewords within relative Hamming distance , where .
List decodability of Reed-Solomon codes up to capacity. For every , there is a constant such that every Reed-Solomon code of length and rate is list-decodable from a fraction of errors with list size at most . Equivalently,
This conjecture proposes list decodability up to the information-theoretic capacity threshold, with polynomial list size in the block length and inverse gap parameter. The surrounding discussion notes that it is consistent with known limitations and contrasts it with the weaker Johnson-bound guarantee; its resolution status is not specified in the source.
Sources & referencesView supporting material
Primary source
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty and Shubhangi Saraf, “DEEP-FRI: Sampling outside the box improves soundness”, arXiv:1903.12243 (2019).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.