Efficiently List-Decodable Punctured Reed-Muller Codes

DOI10.1109/TIT.2017.2692212MaRDI QIDQ5358572zbMATH OpenOpenAlexFDO

Authors Lingfei Jin, Chaoping Xing, Venkatesan Guruswami

Publication date 21 September 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.00603

Mathematics Subject Classification ID

Communication theory (94A05)

Abstract: The Reed-Muller (RM) code encoding $n$-variate degree-$d$ polynomials over ${mathbbF}_q$ for $d<q$, with its evaluation on ${mathbbF}_q^n$, has relative distance $1-d/q$ and can be list decoded from a $1-O(sqrtd/q)$ fraction of errors. In this work, for $dllq$, 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=Omega(d^2/epsilo{n}^2)$, we given an explicit rate $Omegaleft(fracepsilond!ight)$ puncturing of Reed-Muller codes which have relative distance at least $(1-epsilon)$ and efficient list decoding up to $(1-sqrtepsilon)$ error fraction. This almost matches the performance of random puncturings which work with the weaker field size requirement $q=Omega(d/epsilo{n}^2)$. We can also improve the field size requirement to the optimal (up to constant factors) $q=Omega(d/epsilon)$, at the expense of a worse list decoding radius of $1-epsilo{n}^{1/3}$ and rate $Omegaleft(fracepsilo{n}^{2}d!ight)$. 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.

Cited in

(2)

• List Decoding of&lt;tex&gt;$q$&lt;/tex&gt;-ary Reed–Muller Codes
• BaseFold: efficient field-agnostic polynomial commitment schemes from foldable codes

This page was built for publication: Efficiently List-Decodable Punctured Reed-Muller Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5358572)