Chen–Zhang's optimal list-recovery conjecture for folded Reed–Solomon codes

About 1 year old · traced to

Let θ=L+1−βL+1\theta=\frac{L+1-\beta}{L+1} denote the list-recovery agreement parameter, and let ρ∗\rho^* be defined by

ρ∗=L+1−ℓL+1(1−aRa−1).\rho^*=\frac{L+1-\ell}{L+1}\left(1-\frac{aR}{a-1}\right).

For constants ϵ>0\epsilon>0, elloindent≥2ell\rm oindent\ge 2, L+1=ℓaL+1=\ell^a with a∈N≥2a\in\mathbb{N}^{\ge 2}, R≤a−1aR\leq\frac{a-1}{a}, and a generator gammagamma of Fq×\mathbb{F}^{\times}_q, there is a constant CC such that, whenever s≥Cs\ge C, (k−1)/s≥a(k-1)/s\ge a, and nn is sufficiently large, every rate-RR folded Reed–Solomon code

FRSn,ks,γ(α1,α2,…,αn)\mathsf{FRS}^{s,\gamma}_{n,k}(\alpha_1,\alpha_2,\dots,\alpha_n)

with appropriate evaluation points in Fq\mathbb{F}_q is (ρ∗−ε,ℓ,L)(\rho^*-\varepsilon,\ell,L) list-recoverable.

Chen–Zhang's conjecture. For the stated parameters, folded Reed–Solomon codes achieve list-recovery radius arbitrarily close to ρ∗\rho^* with input list size ellell and output list size LL. The conjecture predicts the optimal tradeoff for these structured codes; its status is not resolved in the supplied source.

References

Primary source

Joshua Brakensiek, Yeyuan Chen, Manik Dhar and Zihan Zhang, “Combinatorial Bounds for List Recovery via Discrete Brascamp–Lieb Inequalities”, arXiv:2510.13775 (2025).

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.