ﻻ يوجد ملخص باللغة العربية
We propose a framework to study the effect of local recovery requirements of codeword symbols on the dimension of linear codes, based on a combinatorial proxy that we call emph{visible rank}. The locality constraints of a linear code are stipulated by a matrix $H$ of $star$s and $0$s (which we call a stencil), whose rows correspond to the local parity checks (with the $star$s indicating the support of the check). The visible rank of $H$ is the largest $r$ for which there is a $r times r$ submatrix in $H$ with a unique generalized diagonal of $star$s. The visible rank yields a field-independent combinatorial lower bound on the rank of $H$ and thus the co-dimension of the code. We prove a rank-nullity type theorem relating visible rank to the rank of an associated construct called emph{symmetric spanoid}, which was introduced by Dvir, Gopi, Gu, and Wigderson~cite{DGGW20}. Using this connection and a construction of appropriate stencils, we answer a question posed in cite{DGGW20} and demonstrate that symmetric spanoid rank cannot improve the currently best known $widetilde{O}(n^{(q-2)/(q-1)})$ upper bound on the dimension of $q$-query locally correctable codes (LCCs) of length $n$. We also study the $t$-Disjoint Repair Group Property ($t$-DRGP) of codes where each codeword symbol must belong to $t$ disjoint check equations. It is known that linear $2$-DRGP codes must have co-dimension $Omega(sqrt{n})$. We show that there are stencils corresponding to $2$-DRGP with visible rank as small as $O(log n)$. However, we show the second tensor of any $2$-DRGP stencil has visible rank $Omega(n)$, thus recovering the $Omega(sqrt{n})$ lower bound for $2$-DRGP. For $q$-LCC, however, the $k$th tensor power for $kle n^{o(1)}$ is unable to improve the $widetilde{O}(n^{(q-2)/(q-1)})$ upper bound on the dimension of $q$-LCCs by a polynomial factor.
Locally recoverable codes were introduced by Gopalan et al. in 2012, and in the same year Prakash et al. introduced the concept of codes with locality, which are a type of locally recoverable codes. In this work we introduce a new family of codes wit
In this work we present a class of locally recoverable codes, i.e. codes where an erasure at a position $P$ of a codeword may be recovered from the knowledge of the entries in the positions of a recovery set $R_P$. The codes in the class that we defi
A new type of spatially coupled low-density parity-check (SC-LDPC) codes motivated by practical storage applications is presented. SC-LDPCL codes (suffix L stands for locality) can be decoded locally at the level of sub-blocks that are much smaller t
Node failures are inevitable in distributed storage systems (DSS). To enable efficient repair when faced with such failures, two main techniques are known: Regenerating codes, i.e., codes that minimize the total repair bandwidth; and codes with local
This paper extends the study of rank-metric codes in extension fields $mathbb{L}$ equipped with an arbitrary Galois group $G = mathrm{Gal}(mathbb{L}/mathbb{K})$. We propose a framework for studying these codes as subspaces of the group algebra $mathb