  This paper considers '$\delta$-almost Reed-Muller codes', i.e., linear codes
spanned by evaluations of all but a $\delta$ fraction of monomials of degree at
most $d$. It is shown that for any $\delta > 0$ and any $\varepsilon>0$, there
exists a family of $\delta$-almost Reed-Muller codes of constant rate that
correct $1/2-\varepsilon$ fraction of random errors with high probability. For
exact Reed-Muller codes, the analogous result is not known and represents a
weaker version of the longstanding conjecture that Reed-Muller codes achieve
capacity for random errors (Abbe-Shpilka-Wigderson STOC '15). Our approach is
based on the recent polarization result for Reed-Muller codes, combined with a
combinatorial approach to establishing inequalities between the Reed-Muller
code entropies.
