
























The Reed-Muller (RM) code encoding $n$-variate degree-$d$ polynomials over ${\mathbb F}_q$ for $d < q$, with its evaluation on ${\mathbb F}_q^n$, has relative distance $1-d/q$ and can be list decoded from a $1-O(\sqrt{d/q})$ fraction of errors. In this work, for $d \ll q$, we give a length-efficient puncturing of such codes which (almost) retains the distance and list decodability properties of the Reed-Muller code, but has much better rate. Specificially, when $q =Ω( d^2/ε^2)$, we given an explicit rate $Ω\left(\fracε{d!}\right)$ puncturing of Reed-Muller codes which have relative distance at least $(1-ε)$ and efficient list decoding up to $(1-\sqrtε)$ error fraction. This almost matches the performance of random puncturings which work with the weaker field size requirement $q= Ω( d/ε^2)$. We can also improve the field size requirement to the optimal (up to constant factors) $q =Ω( d/ε)$, at the expense of a worse list decoding radius of $1-ε^{1/3}$ and rate $Ω\left(\frac{ε^2}{d!}\right)$. The first of the above trade-offs is obtained by substituting for the variables functions with carefully chosen pole orders from an algebraic function field; this leads to a puncturing for which the RM code is a subcode of a certain algebraic-geometric code (which is known to be efficiently list decodable). The second trade-off is obtained by concatenating this construction with a Reed-Solomon based multiplication friendly pair, and using the list recovery property of algebraic-geometric codes.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。