Efficiently List-Decodable Punctured Reed-Muller Codes.

The Reed–Muller (RM) code, encoding n -variate degree- d polynomials over \mathbb Fq for d < q , with its evaluation on \mathbb Fq^{n} , has a relative distance 1-d/q and can be list decoded from a 1-O(\sqrt {d/q}) fraction of errors. In this paper, for d \ll q , we give a length-efficient puncturing of such codes, which (almost) retains the distance and list decodability properties of the RM code, but has a much better rate. Specifically, when q =\Omega ( d^2/ \varepsilon ^2) , we give an explicit rate \Omega \left (\frac \varepsilon d!\right ) puncturing of RM codes, which have a relative distance at least (1- \varepsilon ) and efficient list decoding up to (1-\sqrt { \varepsilon }) error fraction. This almost matches the performance of random puncturings, which work with the weaker field size requirement q= \Omega ( d/ \varepsilon ^{2}) . We can also improve the field size requirement to the optimal (up to constant factors) q =\Omega ( d/ \varepsilon ) , at the expense of a worse list decoding radius of 1- \varepsilon ^{1/3} and rate \Omega \left ({\frac { \varepsilon ^{2}}{d!}}\right )$ . The first of the above tradeoffs 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 tradeoff is obtained by concatenating this construction with a Reed–Solomon-based multiplication friendly pair, and using the list recovery property of algebraic-geometric codes. [ABSTRACT FROM PUBLISHER]