2025/08/18 by Vikrant Ashvinkumar, Ashvinkumar, Vikrant, Shashank Srivastava +2 · 1 citation
Computer Science · Engineering · #Coding theory and cryptography #Cryptography and Data Security #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2508.12548
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-ε. We present a deterministic decoder that runs in near-linear time \widetildeOε(n), improving upon the best-known runtime nΩ(1/ε) for decoding FRS codes. Prior to our work, no capacity achieving code was known whose deterministic decoding could be done in time \widetildeOε(n). We also present a randomized decoder that runs in fully polynomial time poly(1/ε) ⋅ \widetildeO(n), improving the best-known runtime exp(1/ε)⋅ \widetildeO(n) for decoding FRS codes. Again, prior to our work, no capacity achieving code was known whose decoding time depended polynomially on 1/ε. Our results are based on improved pruning procedures for finding the list of codewords inside a constant-dimensional affine subspace.