{
  "annotation_id": "07471820-8c5c-41e4-b10d-e3dff48b87d8",
  "date_created": "2026-02-17T05:53:24.220000Z",
  "date_modified": "2026-02-17T05:53:24.220000Z",
  "file_hash": "097b71403309fbde76896fb6e14d087f83383a9bc6b27729c13bc8746a24140d",
  "private": false,
  "record": {
    "abstract": "A collection of sets satisfies a $(\\delta,\\varepsilon)$-proximity gap with respect to some property if for every set in the collection, either (i) all members of the set are $\\delta$-close to the property in (relative) Hamming distance, or (ii) only a small $\\varepsilon$-fraction of members are $\\delta$-close to the property.\n  In a seminal work, Ben-Sasson \\textit{et al.}\\ showed that the collection of affine subspaces exhibits a $(\\delta,\\varepsilon)$-proximity gap with respect to the property of being Reed--Solomon (RS) codewords with $\\delta$ 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.\n  Folded Reed--Solomon (FRS) codes are known to achieve the optimal list decoding radius $\\delta$, 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 $(\\delta,\\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).\n  An additional motivation to understand proximity gaps for FRS codes is the recent results [BCDZ\u002725] 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\u002725], as well as codes over constant-size alphabet based on AEL [JS\u002725].",
    "arxiv_id": "2601.10047",
    "authors": [
      "Fernando Granha Jeronimo",
      "Lenny Liu",
      "Pranav Rajpal"
    ],
    "categories": [
      "cs.IT",
      "cs.CC",
      "math.IT"
    ],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "title": "Optimal Proximity Gap for Folded Reed--Solomon Codes via Subspace Designs",
    "url": "https://arxiv.org/abs/2601.10047",
    "version": "v1"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "2efc868d-592e-40e9-a759-a582d9d05cdc",
    "id": "arXiv Dataset",
    "type": "Model",
    "variant": "snapshot-2026-01-17",
    "version": "0.1.0"
  },
  "user_id": 1000002
}