← All problems

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

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
  1. 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.