Back to Search
Start Over
The List Decoding Radius for Reed–Muller Codes Over Small Fields.
- Source :
-
IEEE Transactions on Information Theory . Jun2018, Vol. 64 Issue 6, p4382-4391. 10p. - Publication Year :
- 2018
-
Abstract
- 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]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 64
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 129840953
- Full Text :
- https://doi.org/10.1109/TIT.2018.2822686