Tighter List-Size Bounds for List-Decoding and Recovery of Folded Reed-Solomon and Multiplicity Codes
Itzhak Tamo
Abstract
Folded Reed-Solomon (FRS) and univariate multiplicity codes are prominent polynomial codes over finite fields renowned for achieving list decoding capacity. These codes have found many applications beyond the traditional scope of coding theory. In this paper, we introduce improved bounds on the list size for list decoding these codes, achieved through a more streamlined proof method. Additionally, we refine an existing randomized algorithm to output the codewords on the list, which enhances its success probability and reduces its running time. Lastly, we establish list-size bounds for a fixed decoding parameter. Notably, our results demonstrate that FRS codes asymptotically attain the generalized Singleton bound for a list of size 2 over a relatively small alphabet, marking the first explicit instance of a code with this property.