Almost-Reed–Muller Codes Achieve Constant Rates for Random Errors
Emmanuel A. Abbe, Jan Hązła, Ido Nachum · IEEE Transactions on Information Theory · 2021
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 proof 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.