论文标题
使用偏斜多项式改善了最大可回收的LRC
Improved Maximally Recoverable LRCs using Skew Polynomials
论文作者
论文摘要
a $（n，r，h，a，q）$ - 本地重建代码（LRC）是长度$ n $的$ \ mathbb {f} _q $上的线性代码，其代码字符号将其码为$ n/r $本地组，每个大小$ r $。每个本地组都满足``$ a $ a $'本地均等支票''从该本地组中的``$ a $'擦除''中恢复，并且还有其他$ h $全球奇偶校验支票可从更全球的擦除模式中提供容错。这样的LRC是最大可回收的（MR），如果它提供了当地和全球擦除弹性的最佳融合 - 即，鉴于当地结构，它可以纠正所有恢复是信息可行的所有擦除模式（这些是准确的模式，这些模式是每个本地组中的$ $ $ a $ a $ a $ a $ a $ h $ h $ h $ h $ codeew）。 随机构造可以轻松地显示出在很大的领域上LRC的存在，但是一个主要的代数挑战是在较小的田地上构建LRC先生，甚至显示其存在，并了解其田间大小的固有下限。我们给出了$（n，r，h，a，q）$的明确结构，其lrcs Mr lrcs具有$ \ left（o \ left（\ max \ {r，n/r \} \ right）\ right）\ right）\ right）这在许多相关参数范围内改善了已知构造。此外，它与Gopi等人的下限匹配。 （2020）在有趣的参数范围内其中，其中$ r =θ（\ sqrt {n}）$，$ r-a =θ（\ sqrt {n}）$和$ h $是一个固定常数，具有$ h \ le a+a+a+a+a+a+a+a+a+a+a+2 $，达到了最佳的场大小，达到了$ $θ_{h} {h}（n^n^n^h/2}）。 我们的构建基于偏斜多项式的理论。我们认为，偏斜多项式在编码和复杂性理论中应该进一步应用。作为一个小例证，我们展示了如何在该理论中以统一的方式捕获代数的基础列表列表的基础列表来解码折叠的芦苇 - 固体代码和多样性代码。
An $(n,r,h,a,q)$-Local Reconstruction Code (LRC) is a linear code over $\mathbb{F}_q$ of length $n$, whose codeword symbols are partitioned into $n/r$ local groups each of size $r$. Each local group satisfies `$a$' local parity checks to recover from `$a$' erasures in that local group and there are further $h$ global parity checks to provide fault tolerance from more global erasure patterns. Such an LRC is Maximally Recoverable (MR), if it offers the best blend of locality and global erasure resilience -- namely it can correct all erasure patterns whose recovery is information-theoretically feasible given the locality structure (these are precisely patterns with up to `$a$' erasures in each local group and an additional $h$ erasures anywhere in the codeword). Random constructions can easily show the existence of MR LRCs over very large fields, but a major algebraic challenge is to construct MR LRCs, or even show their existence, over smaller fields, as well as understand inherent lower bounds on their field size. We give an explicit construction of $(n,r,h,a,q)$-MR LRCs with field size $q$ bounded by $\left(O\left(\max\{r,n/r\}\right)\right)^{\min\{h,r-a\}}$. This improves upon known constructions in many relevant parameter ranges. Moreover, it matches the lower bound from Gopi et al. (2020) in an interesting range of parameters where $r=Θ(\sqrt{n})$, $r-a=Θ(\sqrt{n})$ and $h$ is a fixed constant with $h\le a+2$, achieving the optimal field size of $Θ_{h}(n^{h/2}).$ Our construction is based on the theory of skew polynomials. We believe skew polynomials should have further applications in coding and complexity theory; as a small illustration we show how to capture algebraic results underlying list decoding folded Reed-Solomon and multiplicity codes in a unified way within this theory.
