{"ID":2880911,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.12548","arxiv_id":"2508.12548","title":"Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes","abstract":"Folded Reed-Solomon (FRS) codes are a well-studied family of codes, known for achieving list decoding capacity. In this work, we give improved deterministic and randomized algorithms for list decoding FRS codes of rate $R$ up to radius $1-R-\\varepsilon$. We present a deterministic decoder that runs in near-linear time $\\widetilde{O}_{\\varepsilon}(n)$, improving upon the best-known runtime $n^{Ω(1/\\varepsilon)}$ for decoding FRS codes. Prior to our work, no capacity achieving code was known whose deterministic decoding could be done in time $\\widetilde{O}_{\\varepsilon}(n)$. We also present a randomized decoder that runs in fully polynomial time $\\mathrm{poly}(1/\\varepsilon) \\cdot \\widetilde{O}(n)$, improving the best-known runtime $\\mathrm{exp}(1/\\varepsilon)\\cdot \\widetilde{O}(n)$ for decoding FRS codes. Again, prior to our work, no capacity achieving code was known whose decoding time depended polynomially on $1/\\varepsilon$. Our results are based on improved pruning procedures for finding the list of codewords inside a constant-dimensional affine subspace.","short_abstract":"Folded Reed-Solomon (FRS) codes are a well-studied family of codes, known for achieving list decoding capacity. In this work, we give improved deterministic and randomized algorithms for list decoding FRS codes of rate $R$ up to radius $1-R-\\varepsilon$. We present a deterministic decoder that runs in near-linear time...","url_abs":"https://arxiv.org/abs/2508.12548","url_pdf":"https://arxiv.org/pdf/2508.12548v2","authors":"[\"Vikrant Ashvinkumar\",\"Mursalin Habib\",\"Shashank Srivastava\"]","published":"2025-08-18T01:03:00Z","proceeding":"cs.IT","tasks":"[\"cs.IT\",\"cs.DS\"]","methods":"[]","has_code":false}