List decodability of Reed-Solomon codes up to capacity

Let Fq\mathbb{F}_q be a finite field and let DFqD\subseteq\mathbb{F}_q be an evaluation set. For rate ρ>0\rho>0, write RS[Fq,D,ρ]\mathsf{RS}[\mathbb{F}_q,D,\rho] for the corresponding Reed-Solomon code, and let L(Fq,D,d,δ){\mathcal L}(\mathbb{F}_q,D,d,\delta) denote the maximum, over received words, of the number of codewords within relative Hamming distance δ\delta, where d=ρDd=\rho|D|.

List decodability of Reed-Solomon codes up to capacity. For every ρ>0\rho>0, there is a constant CρC_\rho such that every Reed-Solomon code of length nn and rate ρ\rho is list-decodable from a 1ρε1-\rho-\varepsilon fraction of errors with list size at most (nε)Cρ\left(\frac{n}{\varepsilon}\right)^{C_\rho}. Equivalently,

L(Fq,D,d=ρD,1ρε)(Dε)Cρ.{\mathcal L}(\mathbb{F}_q,D,d=\rho|D|,1-\rho-\varepsilon)\leq\left(\frac{|D|}{\varepsilon}\right)^{C_\rho}.

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.