{
  "abstract": "For any desired rate $R \\in (0,1)$, and gap to list-decoding capacity $\\varepsilon > 0$, we give an explicit $n^{O_{\\varepsilon}(1)}$ time construction of Reed-Solomon codes over extension fields of size polynomial in the block length $n$ that can be list-decoded from a fraction $1-R-\\varepsilon$ of errors with the optimal list-size of $O(\\frac{1-R}{\\varepsilon})$. We also give a simpler, strongly explicit construction of evaluation points for which the associated Reed-Solomon code can be list-decoded from $1-R-\\varepsilon$ errors with list size $(1/\\varepsilon)^{O(1/\\varepsilon)}$. We provide a deterministic list-decoding algorithm for both constructions running in time $O_ε(1)\\mathsf{poly}(n)$. In fact, our Reed-Solomon codes are near-optimal subspace-design codes over a subfield. Via known results, this directly implies the combinatorial list-decoding guarantee, as well as near-optimal list-recovery bounds. We also present a new reduction showing that the subspace-design guarantee also implies line decoding over the extension field itself, which then yields proximity gaps and mutual correlated agreement up to proximity parameter approaching the optimal $1-R$ radius. Compared to the recent algorithm of Brakensiek, Chen, Putterman, Zhang, and Zheng (2026), which list decodes every Reed-Solomon code over prime fields up to capacity, our approach achieves constant (in fact, near-optimal) list size rather than a polynomially growing one, at the cost of carefully choosing the code's evaluation points. In a companion paper, we show that these respective restrictions are unavoidable.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2610.36215",
  "author_total": 3,
  "authors": [
    {
      "name": "Omar Alrabiah"
    },
    {
      "name": "Rohan Goyal"
    },
    {
      "name": "Venkatesan Guruswami"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/6v2vh559yhhsm.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2610.36215",
  "fulltext_url": null,
  "id": "6v2vh559yhhsm",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2610.36215",
  "language": null,
  "licence": "CC-BY-NC-SA-4.0",
  "licence_label": "CC BY-NC-SA 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by-nc-sa/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.CC"
    ],
    [
      "arxiv",
      "cs.IT"
    ],
    [
      "arxiv",
      "math.IT"
    ],
    [
      "openalex",
      "1702|Coding theory and cryptography"
    ]
  ],
  "openalex": "W7224133624",
  "pdf_url": "https://arxiv.org/pdf/2610.36215",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-26",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/6v2vh559yhhsm.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:35:53Z",
      "native_id": "2610.36215",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2610.36215"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.IT",
      "subfield": "general"
    }
  ],
  "title": "Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding",
  "title_text": "Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding",
  "type": "preprint",
  "updated_at": "2026-10-30T12:35:53Z",
  "url": "https://research.draconitic.com/paper/6v2vh559yhhsm",
  "venue": "arXiv",
  "versions": []
}