Efficiently List-Decodable Punctured Reed-Muller Codes
Venkatesan Guruswami, Lingfei Jin, Chaoping Xing · IEEE Transactions on Information Theory · 2017
The Reed-Muller (RM) code, encoding n-variate degree-d polynomials over Fqfor dqn, has a relative distance 1 - d/q and can be list decoded from a 1- O(√d/q) fraction of errors. In this paper, for d ≪ 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 = Ω(d2/ε2), we give an explicit rate Ω (ε/d!) puncturing of RM codes, which have a relative distance at least (1 - √ε) and efficient list decoding up to (1 - √ε) 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/3and rate Ω (ε/d!). 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.