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 {m \choose {\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 ${m \choose {\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 ${m \choose{\leq r}} - {{\log_2 k}\choose {\leq r}} \gg {m\choose{\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 {m\choose {\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 {m\choose {\leq m-(d/2)}}$ random errors for the same range of parameters.

Fixed References

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 {m \choose {\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 ${m \choose {\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 ${m \choose{\leq r}} - {{\log_2 k}\choose {\leq r}} \gg {m\choose{\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 {m\choose {\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 {m\choose {\leq m-(d/2)}}$ random errors for the same range of parameters.