Abbe, EmmanuelHazla, JanNachum, Ido2021-12-042021-12-042021-12-042021-12-0110.1109/TIT.2021.3116663https://infoscience.epfl.ch/handle/20.500.14299/183538WOS:000720518300028This 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 epsilon > 0, there exists a family of delta-almost Reed-Muller codes of constant rate that correct 1/2-epsilon 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.Computer Science, Information SystemsEngineering, Electrical & ElectronicComputer ScienceEngineeringreed-muller codespolarizationcapacitytext::journal::journal article::research article