Slackened Reed–Solomon list-decoding conjecture

Let LL be a positive integer, let C1C\geq1 be a positive real, and let R=knR=\frac{k}{n} be the rate of an [n,k][n,k] Reed–Solomon code. A code is list-decodable from radius ρ\rho with list size LL if every received word has at most LL codewords within relative Hamming distance ρ\rho. Slackened Reed–Solomon list-decoding conjecture. For sufficiently large qq, for most evaluation tuples (α1,,αn)Fqn(\alpha_1,\ldots,\alpha_n)\in\mathbb{F}_q^n, the [n,k][n,k] Reed–Solomon code evaluated on this tuple is (LL+1(1CR),L)(\frac{L}{L+1}(1-CR),L)-list decodable. The conjecture is a relaxation of the capacity prediction by allowing the slack factor CC; the paper presents it as open and proves only partial parameterized results.

Sources & referencesView supporting material

Primary source

Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo and Mary Wootters, “Improved List-Decodability of Reed–Solomon Codes via Tree Packings”, arXiv:2011.04453 (2023).

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.