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

About 1 year old · traced to

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

{c∈C∣Δ(c,L1×L2×⋯×Ln)<1−R−ε}\{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:

{c∈C∣Δ(c,L1×L2×⋯×Ln)<1−R−ε}=⋃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.

References

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.