ECCC-Report TR16-051https://eccc.weizmann.ac.il/report/2016/051Comments and Revisions published for TR16-051en-usFri, 10 May 2019 14:44:17 +0300
Revision 4
| Efficient Multi-Point Local Decoding of Reed-Muller Codes via Interleaved Codex |
Ronald Cramer,
Chaoping Xing,
chen yuan
https://eccc.weizmann.ac.il/report/2016/051#revision4Reed-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^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,,to get the same success probability from repetition of local decoding for recovery of a single coordinate, one has to query $O(qk^2)$ coordinates. Thus, the query complexity of our local decoding is smaller for $k=\Omega(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). Our estimation of success error probability is based on error probability bound for $t$-wise linearly independent variables given in \cite{BR94}.Fri, 10 May 2019 14:44:17 +0300https://eccc.weizmann.ac.il/report/2016/051#revision4
Revision 3
| On Multi-Point Local Decoding of Reed-Muller Codes |
Ronald Cramer,
Chaoping Xing,
chen yuan
https://eccc.weizmann.ac.il/report/2016/051#revision3Reed-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 evaluation polynomials of total degree $d\lesssim\Gs\sqrt{q}$ for some $\Gs\in(0,1)$. By introducing a local decoding of Reed-Muller codes via the concept of codex that has been used for arithmetic secret sharing \cite{C11,CCX12}, we are able to locally recover arbitrarily large number $k$ of coordinates simultaneously at the cost of querying $O(k\sqrt{q})$ coordinates, where $q$ is the code alphabet size. 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. In contrast, by repetition of local decoding for recovery of a single coordinate, one has to query $\Omega(k\sqrt{q}\log k/\log q)$ coordinates for $k=q^{\Omega(\sqrt{q})}$ (and query $O(kq)$ coordinates for $k=q^{O(\sqrt{q})}$, respectively). 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 from repetition of local decoding for recovery of a single coordinate, one has to query $O(k^2\sqrt{q}\log k/\log q)$ coordinates (or $O(k^2q)$ coordinates for $k=q^{O(\sqrt{q})}$, respectively). In addition, our local decoding also works for recovery of one single coordinate as well and it gives a better success probability than the one by repetition of local decoding on curves. The main tool to realize codex is based on algebraic function fields (or more precisely, algebraic geometry codes). Our estimation of success error probability is based on error probability bound for $t$-wise linearly independent variables given in \cite{BR94}.Fri, 10 May 2019 14:23:32 +0300https://eccc.weizmann.ac.il/report/2016/051#revision3
Revision 2
| Efficient Multi-Point Local Decoding of Reed-Muller Codes via Interleaved Codex |
Ronald Cramer,
Chaoping Xing,
chen yuan
https://eccc.weizmann.ac.il/report/2016/051#revision2Reed-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^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, to get the same success probability from repetition of local decoding for recovery of a single coordinate, one has to query $O(qk^2)$ coordinates. Thus, the query complexity of our local decoding is smaller for $k=\Omega(q)$. In addition, our local decoding 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). Our estimation of success error probability is based on error probability bound for $t$-wise linearly independent variables given in \cite{BR94}.
Fri, 17 Mar 2017 06:31:27 +0200https://eccc.weizmann.ac.il/report/2016/051#revision2
Revision 1
| Efficient Multi-Point Local Decoding of Reed-Muller Codes via Interleaved Codex |
Ronald Cramer,
Chaoping Xing,
chen yuan
https://eccc.weizmann.ac.il/report/2016/051#revision1Reed-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.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^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,to get the same success probability from repetition of local decoding for recovery of a single coordinate, one has to query $O(qk^2)$ coordinates. Thus, the query complexity of our local decoding is smaller for $k=\Omega(q)$. In addition, our local decoding 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). Our estimation of success error probability is based on error probability bound for $t$-wise linearly independent variables given in \cite{BR94}.Wed, 15 Mar 2017 16:26:21 +0200https://eccc.weizmann.ac.il/report/2016/051#revision1
Paper TR16-051
| On Multi-Point Local Decoding of Reed-Muller Codes |
Ronald Cramer,
Chaoping Xing,
chen yuan
https://eccc.weizmann.ac.il/report/2016/051Reed-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 evaluation polynomials of total degree $d\lesssim\Gs\sqrt{q}$ for some $\Gs\in(0,1)$. By introducing a local decoding of Reed-Muller codes via the concept of codex that has been used for arithmetic secret sharing \cite{C11,CCX12}, we are able to locally recover arbitrarily large number $k$ of coordinates simultaneously at the cost of querying $O(k\sqrt{q})$ coordinates, where $q$ is the code alphabet size. 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. In contrast, by repetition of local decoding for recovery of a single coordinate, one has to query $\Omega(k\sqrt{q}\log k/\log q)$ coordinates for $k=q^{\Omega(\sqrt{q})}$ (and query $O(kq)$ coordinates for $k=q^{O(\sqrt{q})}$, respectively). 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 from repetition of local decoding for recovery of a single coordinate, one has to query $O(k^2\sqrt{q}\log k/\log q)$ coordinates (or $O(k^2q)$ coordinates for $k=q^{O(\sqrt{q})}$, respectively). In addition, our local decoding also works for recovery of one single coordinate as well and it gives a better success probability than the one by repetition of local decoding on curves. The main tool to realize codex is based on algebraic function fields (or more precisely, algebraic geometry codes). Our estimation of success error probability is based on error probability bound for $t$-wise linearly independent variables given in \cite{BR94}.Thu, 07 Apr 2016 11:11:18 +0300https://eccc.weizmann.ac.il/report/2016/051