Almost-Reed--Muller Codes Achieve Constant Rates for Random Errors

Emmanuel Abbe, Jan Hązła, Ido Nachum

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 an…