  This work proves new results on the ability of binary Reed-Muller codes to
decode from random errors and erasures. We obtain these results by proving
improved bounds on the weight distribution of Reed-Muller codes of high
degrees. Specifically, given weight $\beta \in (0,1)$ we prove an upper bound
on the number of codewords of relative weight at most $\beta$. We obtain new
results in two different settings: for weights $\beta < 1/2$ and for weights
that are close to $1/2$.
  Our new bounds on the weight distribution imply that RM codes with $m$
variables and degree $\gamma m$, for some explicit constant $\gamma$, achieve
capacity for random erasures (i.e. for the binary erasure channel) and for
random errors (for the binary symmetric channel). Earlier, it was known that RM
codes achieve capacity for the binary symmetric channel for degrees $r = o(m)$.
For the binary erasure channel it was known that RM codes achieve capacity for
degree $o(m)$ or $r \in [m/2 \pm O(\sqrt{m})]$. Thus, our result provide a new
range of parameters for which RM achieve capacity for these two well studied
channels. In addition, our results imply that for every $\epsilon > 0$ (in fact
we can get up to $\epsilon = \Omega\left(\sqrt{\frac{\log m}{m}}\right)$) RM
codes of degree $r<(1/2-\epsilon)m$ can correct a fraction of $1-o(1)$ random
erasures with high probability. We also show that, information theoretically,
such codes can handle a fraction of $1/2-o(1)$ random errors with high
probability. Thus, for example, given noisy evaluations of a degree $0.499m$
polynomial, it is possible to interpolate it even if a random $0.499$ fraction
of the evaluations were corrupted, with high probability. While the $o(1)$
terms are not the correct ones to ensure capacity, these results show that RM
codes of such degrees are in some sense close to achieving capacity.
