Low-dimensional sum-set decomposition conjecture for folded Reed–Solomon list recovery

Let d4aad4aa be a folded Reed–Solomon code of rate RR, with folding parameter ss, and let d4a11,,d4a1nd4a1_1,\ldots,d4a1_n be subsets of the alphabet of size d4ced4ce. For a positive integer \ell, let an (r,)(r,\ell) sum-set mean a sum-set with the parameters indicated in the source. For every N\ell\in\mathbb N, bε>0b\varepsilon>0, and R>0R>0, there is an s0=Ω(/ε2)s_0=\Omega(\ell/\varepsilon^2) such that, for every rate-RR ss-folded Reed–Solomon code d4aad4aa with s>s0s>s_0, the list

{cCΔ(c,L1×L2××Ln)<1Rε}\{c\in\mathcal C\mid \Delta(c,L_1\times L_2\times\cdots\times L_n)<1-R-\varepsilon\}

is exactly the union of \poly(/ε)\poly(\ell/\varepsilon) many (O((R+ε)/ε),)(O((R+\varepsilon)/\varepsilon),\ell) sum-sets P1,,PtP_1,\ldots,P_t:

{cCΔ(c,L1×L2××Ln)<1Rε}=i=1tPi.\{c\in\mathcal C\mid \Delta(c,L_1\times L_2\times\cdots\times L_n)<1-R-\varepsilon\}=\bigcup_{i=1}^tP_i.

Low-dimensional sum-set decomposition conjecture. For every choice of N\ell\in\mathbb N, ε>0\varepsilon>0, and R>0R>0, the decomposition above exists for all sufficiently large folding parameters ss, with s0=Ω(/ε2)s_0=\Omega(\ell/\varepsilon^2) and only \poly(/ε)\poly(\ell/\varepsilon) sum-sets. This would give a combinatorial list-recovery bound of \poly(/ε)O(R/ε)\poly(\ell/\varepsilon)\cdot\ell^{O(R/\varepsilon)}, stated in the source to be optimal. The assertion is strong because it requires exact equality with a union of a few low-dimensional sum-sets, rather than mere containment.

Sources & referencesView supporting material

Primary source

Rohan Goyal and Venkatesan Guruswami, “Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes”, arXiv:2512.08017 (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.