Low-dimensional sum-set decomposition conjecture for folded Reed–Solomon list recovery
Low-dimensional sum-set decomposition conjecture for folded Reed–Solomon list recovery
Let be a folded Reed–Solomon code of rate , with folding parameter , and let be subsets of the alphabet of size . For a positive integer , let an sum-set mean a sum-set with the parameters indicated in the source. For every , , and , there is an such that, for every rate- -folded Reed–Solomon code with , the list
is exactly the union of many sum-sets :
Low-dimensional sum-set decomposition conjecture. For every choice of , , and , the decomposition above exists for all sufficiently large folding parameters , with and only sum-sets. This would give a combinatorial list-recovery bound of , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.