Optimal Proximity Gap for Folded Reed--Solomon Codes via Subspace Designs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909990966525952 |
|---|---|
| author | Jeronimo, Fernando Granha Liu, Lenny Rajpal, Pranav |
| author_facet | Jeronimo, Fernando Granha Liu, Lenny Rajpal, Pranav |
| contents | A collection of sets satisfies a $(δ,\varepsilon)$-proximity gap with respect to some property if for every set in the collection, either (i) all members of the set are $δ$-close to the property in (relative) Hamming distance, or (ii) only a small $\varepsilon$-fraction of members are $δ$-close to the property.
In a seminal work, Ben-Sasson \textit{et al.}\ showed that the collection of affine subspaces exhibits a $(δ,\varepsilon)$-proximity gap with respect to the property of being Reed--Solomon (RS) codewords with $δ$ up to the so-called Johnson bound for list decoding. Their technique relies on the Guruswami--Sudan list decoding algorithm for RS codes, which is guaranteed to work in the Johnson bound regime.
Folded Reed--Solomon (FRS) codes are known to achieve the optimal list decoding radius $δ$, a regime known as capacity. Moreover, a rich line of list decoding algorithms was developed for FRS codes. It is then natural to ask if FRS codes can be shown to exhibit an analogous $(δ,\varepsilon)$-proximity gap, but up to the so-called optimal capacity regime. We answer this question in the affirmative (and the framework naturally applies more generally to suitable subspace-design codes).
An additional motivation to understand proximity gaps for FRS codes is the recent results [BCDZ'25] showing that they exhibit properties similar to random linear codes, which were previously shown to be related to properties of RS codes with random evaluation points in [LMS'25], as well as codes over constant-size alphabet based on AEL [JS'25]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_10047 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal Proximity Gap for Folded Reed--Solomon Codes via Subspace Designs Jeronimo, Fernando Granha Liu, Lenny Rajpal, Pranav Information Theory Computational Complexity A collection of sets satisfies a $(δ,\varepsilon)$-proximity gap with respect to some property if for every set in the collection, either (i) all members of the set are $δ$-close to the property in (relative) Hamming distance, or (ii) only a small $\varepsilon$-fraction of members are $δ$-close to the property. In a seminal work, Ben-Sasson \textit{et al.}\ showed that the collection of affine subspaces exhibits a $(δ,\varepsilon)$-proximity gap with respect to the property of being Reed--Solomon (RS) codewords with $δ$ up to the so-called Johnson bound for list decoding. Their technique relies on the Guruswami--Sudan list decoding algorithm for RS codes, which is guaranteed to work in the Johnson bound regime. Folded Reed--Solomon (FRS) codes are known to achieve the optimal list decoding radius $δ$, a regime known as capacity. Moreover, a rich line of list decoding algorithms was developed for FRS codes. It is then natural to ask if FRS codes can be shown to exhibit an analogous $(δ,\varepsilon)$-proximity gap, but up to the so-called optimal capacity regime. We answer this question in the affirmative (and the framework naturally applies more generally to suitable subspace-design codes). An additional motivation to understand proximity gaps for FRS codes is the recent results [BCDZ'25] showing that they exhibit properties similar to random linear codes, which were previously shown to be related to properties of RS codes with random evaluation points in [LMS'25], as well as codes over constant-size alphabet based on AEL [JS'25]. |
| title | Optimal Proximity Gap for Folded Reed--Solomon Codes via Subspace Designs |
| topic | Information Theory Computational Complexity |
| url | https://arxiv.org/abs/2601.10047 |