ECCC-Report TR14-087https://eccc.weizmann.ac.il/report/2014/087Comments and Revisions published for TR14-087en-usThu, 17 Jul 2014 19:34:27 +0300
Revision 1
| List decoding Reed-Muller codes over small fields |
Abhishek Bhowmick,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2014/087#revision1The 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 $RM_{\mathbb{F}}(n,d)$ is defined by $n$-variate degree-$d$ polynomials over $\mathbb{F}$. In this work, we study the list decoding radius of Reed-Muller codes over a constant prime field $\mathbb{F}=\mathbb{F}_p$, 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 $RM_{\mathbb{F}}(n,d)$, then the number of codewords in any ball of radius $\delta(d)-\epsilon$ is bounded by $c=c(p,d,\epsilon)$ independent of $n$. This resolves a conjecture of Gopalan-Klivans-Zuckerman [STOC 2008], who among other results proved it in the special case of $\mathbb{F}=\mathbb{F}_2$; and extends the work of Gopalan [FOCS 2010] 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 $RM_{\mathbb{F}}(n,d)$ in a ball of radius $\delta(e) - \epsilon$ is bounded by $\exp(c \cdot n^{d-e})$, where $c=c(p,d,\epsilon)$ is independent of $n$. The dependence on $n$ is tight. This extends the work of Kaufman-Lovett-Porat [IEEE Inf. Theory 2012] 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 compositions of polynomials.Thu, 17 Jul 2014 19:34:27 +0300https://eccc.weizmann.ac.il/report/2014/087#revision1
Paper TR14-087
| List decoding Reed-Muller codes over small fields |
Abhishek Bhowmick,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2014/087The 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 $RM_{\mathbb{F}}(n,d)$ is defined by $n$-variate degree-$d$ polynomials over $\mathbb{F}$. In this work, we study the list decoding radius of Reed-Muller codes over a constant prime field $\mathbb{F}=\mathbb{F}_p$, 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 $RM_{\mathbb{F}}(n,d)$, then the number of codewords in any ball of radius $\delta(d)-\epsilon$ is bounded by $c=c(p,d,\epsilon)$ independent of $n$. This resolves a conjecture of Gopalan-Klivans-Zuckerman [STOC 2008], who among other results proved it in the special case of $\mathbb{F}=\mathbb{F}_2$; and extends the work of Gopalan [FOCS 2010] 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 $RM_{\mathbb{F}}(n,d)$ in a ball of radius $\delta(e) - \epsilon$ is bounded by $\exp(c \cdot n^{d-e})$, where $c=c(p,d,\epsilon)$ is independent of $n$. The dependence on $n$ is tight. This extends the work of Kaufman-Lovett-Porat [IEEE Inf. Theory 2012] 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 compositions of polynomials.Sat, 12 Jul 2014 16:31:35 +0300https://eccc.weizmann.ac.il/report/2014/087