Paper Info
Title
Efficient Multi-Point Local Decoding of Reed-Muller Codes via Interleaved Codex
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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d=\Theta ({q})$ </tex-math></inline-formula> , where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula> is the code alphabet size (in fact, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d$ </tex-math></inline-formula> can be as big as <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q/4$ </tex-math></inline-formula> 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), we are able to locally recover arbitrarily large number <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> of coordinates of a Reed-Muller code simultaneously with error probability <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\exp (-\Omega (k))$ </tex-math></inline-formula> at the cost of querying merely <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(q^{2}k)$ </tex-math></inline-formula> coordinates. It turns out that our local decoding of Reed-Muller codes shows ( <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">perhaps surprisingly</italic> ) that accessing <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> locations is in fact cheaper than repeating the procedure for accessing a single location for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> times. Precisely speaking, to get the same success probability by repeating the local decoding algorithm of a single coordinate, one has to query <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Omega (qk^{2})$ </tex-math></inline-formula> coordinates. Thus, the query complexity of our local decoding is smaller for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k=\Omega (q)$ </tex-math></inline-formula> . If we impose the same query complexity constraint on both algorithm, our local decoding algorithm yields smaller error probability when <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k=\Omega (q^{q})$ </tex-math></inline-formula> . In addition, our local decoding is efficient, i.e., the decoding complexity is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\mathrm{ Poly}}(k,q)$ </tex-math></inline-formula> . Construction of an interleaved codex is based on concatenation of a codex with a multiplication friendly pair, while the main tool to realize codex is based on algebraic function fields (or more precisely, algebraic geometry codes).
Year
DOI
Venue
2020
10.1109/TIT.2019.2939135
IEEE Transactions on Information Theory
Keywords
Field
DocType
Decoding,Geometry,Reed-Solomon codes,Complexity theory,Error probability,Tools,Poles and towers
Discrete mathematics,Combinatorics,Linear independence,Secret sharing,Sequential decoding,Polynomial,Reed–Muller code,Decoding methods,List decoding,Arbitrarily large,Mathematics
Journal
Volume
Issue
ISSN
66
1
0018-9448
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Ronald Cramer12499178.28
Chaoping Xing2916110.47
Chen Yuan32712.30