Decoding high rate Reed-Muller codes from random errors in near linear time.
Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk · arXiv (Cornell University) · 2015
Reed-Muller codes encode an $m$-variate polynomial of degree $k$ by evaluating it on all points in $\{0,1\}^m$. We denote this code by $RM(m,k)$. For $k=m-r$, its distance is $2^r$ and so it cannot correct more than $2^{r-1}$ errors in the worst case. For random errors one may hope for a better result. Shannon (1948) proved that for codes of the same rate, one cannot correct more than roughly $m^r$ random errors and that there are codes that can correct that many errors. Abbe, Shpilka and Wigderson (2015) showed that about $m^{r/2}$ errors can be corrected for $RM(m,m-r)$, but their result was existential and did not give a decoding algorithm. In this work we give a near linear time algorithm (in the encoding length $n=2^m$) for decoding that many errors. Our algorithm works correctly whenever the error locations satisfy some independence criterion. Using a result of Abbe et al. we get in particular that with high probability over the errors, our algorithm can correct $(1-o(1)){m\choose\leq r}$ random errors in $RM(m,m-(2r+2))$, when $r=O(\sqrt{m/\log m})$. This number of errors is much larger than the distance of the code, $2^{2r+2}$. The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding Reed-Muller codes. It can be seen as a more explicit proof of the result of Abbe et al. for high rate Reed-Muller codes and it also bares some similarities with the Berlekamp-Welch algorithm for decoding Reed-Solomon codes. Furthermore, the proof shows that for any $r$, our algorithm can correct any error pattern in $RM(m,m-(2r+2))$ for which the same erasure pattern can be corrected in $RM(m,m-(r+1))$. Thus if $RM(m,m-(r+1))$ achieves capacity for the Binary Erasure Channel, our algorithm can correct $1-o(1)$ fraction of error patterns of weight $(1-o(1)){m\choose \leq r}$ in $RM(m,m-(2r+2))$.