Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLower Bounds for Maximally Recoverable Tensor Code and Higher Order MDS Codes
149
0
0.0
(
0
)
Added by
Joshua Brakensiek
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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$).
rate research
Read More
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.
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.
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 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.
Secure codes are widely-studied combinatorial structures which were introduced for traitor tracing in broadcast encryption. To determine the maximum size of such structures is the main research objective. In this paper, we investigate the lower bounds for secure codes and their related structures. First, we give some improved lower bounds for the rates of $2$-frameproof codes and $overline{2}$-separable codes for slightly large alphabet size. Then we improve the lower bounds for the rate of some related structures, i.e., strongly $2$-separable matrices and $2$-cancellative set families. Finally, we give a general method to derive new lower bounds for strongly $t$-separable matrices and $t$-cancellative set families for $tge 3.$
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
