2018/11/29 by Ori Sberlo, Sberlo, Ori, Shpilka, Amir
Biochemistry, Genetics and Molecular Biology · Computer Science · #Coding theory and cryptography #Cooperative Communication and Network Coding #DNA and Biological Computing #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1811.12447
openalex publication_date 2018/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This work proves new results on the ability of binary Reed-Muller codes to\ndecode from random errors and erasures. We obtain these results by proving\nimproved bounds on the weight distribution of Reed-Muller codes of high\ndegrees. Specifically, given weight \β \∈ (0,1) we prove an upper bound\non the number of codewords of relative weight at most \β. We obtain new\nresults in two different settings: for weights \β < 1/2 and for weights\nthat are close to 1/2.\n Our new bounds on the weight distribution imply that RM codes with m\nvariables and degree \γ m, for some explicit constant \γ, achieve\ncapacity for random erasures (i.e. for the binary erasure channel) and for\nrandom errors (for the binary symmetric channel). Earlier, it was known that RM\ncodes achieve capacity for the binary symmetric channel for degrees r = o(m).\nFor the binary erasure channel it was known that RM codes achieve capacity for\ndegree o(m) or r \∈ [m/2 \± O(\√(m))]. Thus, our result provide a new\nrange of parameters for which RM achieve capacity for these two well studied\nchannels. In addition, our results imply that for every \ε > 0 (in fact\nwe can get up to \ε = \Ω\(\√(\(\log m)/(m))\)) RM\ncodes of degree r<(1/2-\ε)m can correct a fraction of 1-o(1) random\nerasures with high probability. We also show that, information theoretically,\nsuch codes can handle a fraction of 1/2-o(1) random errors with high\nprobability. Thus, for example, given noisy evaluations of a degree 0.499m\npolynomial, it is possible to interpolate it even if a random 0.499 fraction\nof the evaluations were corrupted, with high probability. While the o(1)\nterms are not the correct ones to ensure capacity, these results show that RM\ncodes of such degrees are in some sense close to achieving capacity.\n