Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImproved Maximally Recoverable LRCs using Skew Polynomials
88
0
0.0
(
0
)
Added by
Sivakanth Gopi
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
An $(n,r,h,a,q)$-Local Reconstruction Code 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(Oleft(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=Theta(sqrt{n})$, $r-a=Theta(sqrt{n})$ and $h$ is a fixed constant with $hle a+2$, achieving the optimal field size of $Theta_{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.
rate research
Read More
An $(m,n,a,b)$-tensor code consists of $mtimes n$ matrices whose columns satisfy `$a$ parity checks and rows satisfy `$b$ parity checks (i.e., a tensor code is the tensor product of a column code and row code). Tensor codes are useful in distributed storage because a single erasure can be corrected quickly either by reading its row or column. Maximally Recoverable (MR) Tensor Codes, introduced by Gopalan et al., are tensor codes which can correct every erasure pattern that is information theoretically possible to correct. The main questions about MR Tensor Codes are characterizing which erasure patterns are correctable and obtaining explicit constructions over small fields. In this paper, we study the important special case when $a=1$, i.e., the columns satisfy a single parity check equation. We introduce the notion of higher order MDS codes (MDS$(ell)$ codes) which is an interesting generalization of the well-known MDS codes, where $ell$ captures the order of genericity of points in a low-dimensional space. We then prove that a tensor code with $a=1$ is MR iff the row code is an MDS$(m)$ code. We then show that MDS$(m)$ codes satisfy some weak duality. Using this characterization and duality, we prove that $(m,n,a=1,b)$-MR tensor codes require fields of size $q=Omega_{m,b}(n^{min{b,m}-1})$. Our lower bound also extends to the setting of $a>1$. We also give a deterministic polynomial time algorithm to check if a given erasure pattern is correctable by the MR tensor code (when $a=1$).
Local Reconstruction Codes (LRCs) allow for recovery from a small number of erasures in a local manner based on just a few other codeword symbols. A maximally recoverable (MR) LRC offers the best possible blend of such local and global fault tolerance, guaranteeing recovery from all erasure patterns which are information-theoretically correctable given the presence of local recovery groups. In an $(n,r,h,a)$-LRC, the $n$ codeword symbols are partitioned into $r$ disjoint groups each of which include $a$ local parity checks capable of locally correcting $a$ erasures. MR LRCs have received much attention recently, with many explicit constructions covering different regimes of parameters. Unfortunately, all known constructions require a large field size that exponential in $h$ or $a$, and it is of interest to obtain MR LRCs of minimal possible field size. In this work, we develop an approach based on function fields to construct MR LRCs. Our method recovers, and in most parameter regimes improves, the field size of previous approaches. For instance, for the case of small $r ll epsilon log n$ and large $h ge Omega(n^{1-epsilon})$, we improve the field size from roughly $n^h$ to $n^{epsilon h}$. For the case of $a=1$ (one local parity check), we improve the field size quadratically from $r^{h(h+1)}$ to $r^{h lfloor (h+1)/2 rfloor}$ for some range of $r$. The improvements are modest, but more importantly are obtained in a unified manner via a promising new idea.
We construct maximally recoverable codes (corresponding to partial MDS codes) which are based on linearized Reed-Solomon codes. The new codes have a smaller field size requirement compared with known constructions. For certain asymptotic regimes, the constructed codes have order-optimal alphabet size, asymptotically matching the known lower bound.
Locally recoverable (LRC) codes have recently been a focus point of research in coding theory due to their theoretical appeal and applications in distributed storage systems. In an LRC code, any erased symbol of a codeword can be recovered by accessing only a small number of other symbols. For LRC codes over a small alphabet (such as binary), the optimal rate-distance trade-off is unknown. We present several new combinatorial bounds on LRC codes including the locality-aware sphere packing and Plotkin bounds. We also develop an approach to linear programming (LP) bounds on LRC codes. The resulting LP bound gives better estimates in examples than the other upper bounds known in the literature. Further, we provide the tightest known upper bound on the rate of linear LRC codes with a given relative distance, an improvement over the previous best known bounds.
We introduce a class of Laurent polynomials, called maximally mutable Laurent polynomials (MMLPs), that we believe correspond under mirror symmetry to Fano varieties. A subclass of these, called rigid, are expected to correspond to Fano varieties with terminal locally toric singularities. We prove that there are exactly 10 mutation classes of rigid MMLPs in two variables; under mirror symmetry these correspond one-to-one with the 10 deformation classes of smooth del~Pezzo surfaces. Furthermore we give a computer-assisted classification of rigid MMLPs in three variables with reflexive Newton polytope; under mirror symmetry these correspond one-to-one with the 98 deformation classes of three-dimensional Fano manifolds with very ample anticanonical bundle. We compare our proposal to previous approaches to constructing mirrors to Fano varieties, and explain why mirror symmetry in higher dimensions necessarily involves varieties with terminal singularities. Every known mirror to a Fano manifold, of any dimension, is a rigid MMLP.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
