Efficient Multi-Point Local Decoding of Reed-Muller Codes via Interleaved Codex

DOI10.1109/TIT.2019.2939135MaRDI QIDQ5211598zbMATH OpenOpenAlexFDO

Authors Ronald Cramer, Chaoping Xing, Chen Yuan

Publication date 28 January 2020

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

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

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Decoding (94B35)

Abstract: Reed-Muller codes are among the most important classes of locally correctable codes. Currently local decoding of Reed-Muller codes is based on decoding on lines or quadratic curves to recover one single coordinate. To recover multiple coordinates simultaneously, the naive way is to repeat the local decoding for recovery of a single coordinate. This decoding algorithm might be more expensive, i.e., require higher query complexity. In this paper, we focus on Reed-Muller codes with usual parameter regime, namely, the total degree of evaluation polynomials is $d=Theta(q)$, where $q$ is the code alphabet size (in fact, $d$ can be as big as $q/4$ in our setting). By introducing a novel variation of codex, i.e., interleaved codex (the concept of codex has been used for arithmetic secret sharing cite{C11,CCX12}), we are able to locally recover arbitrarily large number $k$ of coordinates of a Reed-Muller code simultaneously at the cost of querying $O(q^{2}k)$ coordinates. It turns out that our local decoding of Reed-Muller codes shows ({it perhaps surprisingly}) that accessing $k$ locations is in fact cheaper than repeating the procedure for accessing a single location for $k$ times. Our estimation of success error probability is based on error probability bound for $t$-wise linearly independent variables given in cite{BR94}.

Cited in

(4)

• Succinct arguments for RAM programs via projection codes
• scientific article; zbMATH DE number 6850352 (Why is no real title available?)
• Multiple-Layer Integrated Interleaved Codes: A Class of Hierarchical Locally Recoverable Codes
• Integrated interleaved codes as locally recoverable codes: properties and performance

This page was built for publication: Efficient Multi-Point Local Decoding of Reed-Muller Codes via Interleaved Codex

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