  We study the following natural question on random sets of points in
$\mathbb{F}_2^m$: Given a random set of $k$ points $Z=\{z_1, z_2, \dots, z_k\}
\subseteq \mathbb{F}_2^m$, what is the dimension of the space of degree at most
$r$ multilinear polynomials that vanish on all points in $Z$?
  We show that, for $r \leq \gamma m$ (where $\gamma > 0$ is a small, absolute
constant) and $k = (1-\epsilon) \cdot \binom{m}{\leq r}$ for any constant
$\epsilon > 0$, the space of degree at most $r$ multilinear polynomials
vanishing on a random set $Z = \{z_1,\ldots, z_k\}$ has dimension exactly
$\binom{m}{\leq r} - k$ with probability $1 - o(1)$. This bound shows that
random sets have a much smaller space of degree at most $r$ multilinear
polynomials vanishing on them, compared to the worst-case bound (due to Wei
(IEEE Trans. Inform. Theory, 1991)) of $\binom{m}{\leq r} - \binom{\log_2
k}{\leq r} \gg \binom{m}{\leq r} - k$.
  Using this bound, we show that high-degree Reed-Muller codes
($\text{RM}(m,d)$ with $d > (1-\gamma) m$) "achieve capacity" under the Binary
Erasure Channel in the sense that, for any $\epsilon > 0$, we can recover from
$(1 - \epsilon) \cdot \binom{m}{\leq m-d-1}$ random erasures with probability
$1 - o(1)$. This also implies that $\text{RM}(m,d)$ is also efficiently
decodable from $\approx \binom{m}{\leq m-(d/2)}$ random errors for the same
range of parameters.
