Efficient list decoding of punctured Reed-Muller codes.
Venkatesan Guruswami, Lingfei Jin, Chaoping Xing · arXiv (Cornell University) · 2015
The Reed-Muller (RM) code encoding $n$-variate degree-$d$ polynomials over $\mathbb{F}_q$ for $d < q$ 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 \gtrsim d^2/\epsilon^2$, we given an explicit rate $\Omega_d(\epsilon)$ puncturing of Reed-Muller codes which have relative distance at least $(1-\epsilon)$ and efficient list decoding up to $(1-\sqrt{\epsilon})$ error fraction. This almost matches the performance of random puncturings which work with the weaker field size requirement $q \gtrsim d/\epsilon^2$. We can also improve the field size requirement to the optimal (up to constant factors) $q \gtrsim d/\epsilon$, at the expense of a worse list decoding radius of $1-\epsilon^{1/3}$ and rate $\Omega_d(\epsilon^2)$. 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.