The List Decoding Radius of Reed-Muller Codes over Small Fields
Abhishek Bhowmick, Shachar Lovett · 2015
The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well studied codes, like Reed-Solomon or Reed-Muller codes. Fix a finite field F. The Reed-Muller code RMF(n,d) is defined by n-variate degree-d polynomials over F. In this work, we study the list decoding radius of Reed-Muller codes over a constant prime field F=Fp, constant degree d and large n. We show that the list decoding radius is equal to the minimal distance of the code.