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

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+1L+1(1aRa1).\rho^*=\frac{L+1-\ell}{L+1}\left(1-\frac{aR}{a-1}\right).

For constants ϵ>0\epsilon>0, elloindent2ell\rm oindent\ge 2, L+1=aL+1=\ell^a with aN2a\in\mathbb{N}^{\ge 2}, Ra1aR\leq\frac{a-1}{a}, and a generator gammagamma of Fq×\mathbb{F}^{\times}_q, there is a constant CC such that, whenever sCs\ge C, (k1)/sa(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.

Sources & referencesView supporting material

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.