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

DOI10.1109/TIT.2021.3116663MaRDI QIDQ5032640zbMATH OpenOpenAlexFDO

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

Publication date 17 February 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.09590

Mathematics Subject Classification ID

Linear codes (general theory) (94B05)

Abstract: 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.

Cited in

(3)

• Reed–Muller Codes for Random Erasures and Errors
• Reed-Muller Codes
• A criterion for decoding on the binary symmetric channel

This page was built for publication: Almost-Reed–Muller Codes Achieve Constant Rates for Random Errors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5032640)