  Reed-Muller codes encode an $m$-variate polynomial of degree $r$ by
evaluating it on all points in $\{0,1\}^m$. We denote this code by $RM(m,r)$.
The minimal distance of $RM(m,r)$ is $2^{m-r}$ and so it cannot correct more
than half that number of errors in the worst case. For random errors one may
hope for a better result.
  In this work we give an efficient algorithm (in the block length $n=2^m$) for
decoding random errors in Reed-Muller codes far beyond the minimal distance.
Specifically, for low rate codes (of degree $r=o(\sqrt{m})$) we can correct a
random set of $(1/2-o(1))n$ errors with high probability. For high rate codes
(of degree $m-r$ for $r=o(\sqrt{m/\log m})$), we can correct roughly $m^{r/2}$
errors.
  More generally, for any integer $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))$. The results above are obtained by applying recent results
of Abbe, Shpilka and Wigderson (STOC, 2015), Kumar and Pfister (2015) and
Kudekar et al. (2015) regarding the ability of Reed-Muller codes to correct
random erasures.
  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 that are based on the recursive structure of the code. It can
be seen as a more explicit proof of a result of Abbe et al. that shows a
reduction from correcting erasures to correcting errors, and it also bares some
similarities with the famous Berlekamp-Welch algorithm for decoding
Reed-Solomon codes.
