The List Decoding Radius for Reed–Muller Codes Over Small Fields.

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 \mathbb F . The Reed–Muller code \text RM {\mathbb {F}}(n,d) is defined by n -variate degree- d polynomials over \mathbb F . In this paper, we study the list decoding radius of Reed–Muller codes over a constant prime field \mathbb F= \mathbb Fp , constant degree d , and large n . We show that the list decoding radius is equal to the minimal distance of the code. That is, if we denote by {\delta }(d) the normalized minimal distance of \text RM {\mathbb {F}}(n,d) , then the number of codewords in any ball of radius {\delta }(d)- {\varepsilon } is bounded by c=c(p,d, \varepsilon ) independent of n . This resolves a conjecture of Gopalan et al., who among other results proved it in the special case of \mathbb F= \mathbb F2 ; and extends the work of Gopalan who proved the conjecture in the case of d=2 . We also analyse the number of codewords in balls of radius exceeding the minimal distance of the code. For e \leq d , we show that the number of codewords of \text RM \mathbb F(n,d) in a ball of radius \delta (e) - \varepsilon is bounded by \exp (c \cdot n^d-e) , where c=c(p,d, \varepsilon ) is independent of $n$ . The dependence on n$ is tight. This extends the work of Kaufman et al. who proved similar bounds over {\mathbb {F}}_{2} . The proof relies on several new ingredients: an extension of the Frieze–Kannan weak regularity to general function spaces, higher order Fourier analysis, and an extension of the Schwartz–Zippel lemma to the compositions of polynomials. [ABSTRACT FROM PUBLISHER]