Welcome to the resource topic for 2016/369
Title:
Efficient Multi-Point Local Decoding of Reed-Muller Codes via Interleaved Codex
Authors: Ronald Cramer, Chaoping Xing, Chen Yuan
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 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. %Precisely speaking, to correct arbitrarily large number k of coordinates simultaneously by repetition of local decoding for recovery of a single coordinate, one has to query \Omega(k\sqrt{q}\log k/\log q) coordinates, where q is the code alphabet size. 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). %the usual parameter regime where the number m of variables of evaluation polynomials is much bigger than the code alphabet size q and total degree of polynomials is d=\Theta({q}). 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 with error probability \exp(-\Omega(k)) at the cost of querying merely O(q^2k) 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. Precisely speaking, %by repetition of local decoding for recovery of a single coordinate, one has to query \Omega(qk\log k/\log q) coordinates (thus, the query complexity of our local decoding becomes cheaper for k=\Omega(q^q)). Furthermore, our decoding success probability is 1-\Ge with \Ge=O\left(\left(\frac1{\sqrt{q}}\right)^k\right). to get the same success probability by repeating the local decoding algorithm of a single coordinate, one has to query \Omega(qk^2) coordinates. Thus, the query complexity of our local decoding is smaller for k=\Omega(q). If we impose the same query complexity constraint on both algorithm, our local decoding algorithm yields smaller error probability when k=\Omega(q^q). In addition, our local decoding is efficient, i.e., the decoding complexity is \poly(k,q). 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).
ePrint: https://eprint.iacr.org/2016/369
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .