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 :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 153731619
- Full Text :
- https://doi.org/10.1109/TIT.2021.3116663