Back to Search
Start Over
Almost-Reed–Muller Codes Achieve Constant Rates for Random Errors.
- Source :
- IEEE Transactions on Information Theory; Dec2021, Vol. 67 Issue 12, p8034-8050, 17p
- Publication Year :
- 2021
-
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 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- REED-Muller codes
LINEAR codes
ERROR rates
ERROR probability
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 67
- Issue :
- 12
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 153731619
- Full Text :
- https://doi.org/10.1109/TIT.2021.3116663