ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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 epsilon>0epsilon>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∗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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.