ECCC-Report TR21-119https://eccc.weizmann.ac.il/report/2021/119Comments and Revisions published for TR21-119en-usFri, 20 Oct 2023 01:17:07 +0300
Revision 2
| Visible Rank and Codes with Locality |
Omar Alrabiah,
Venkatesan Guruswami
https://eccc.weizmann.ac.il/report/2021/119#revision2We 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 $0$'s and $\star$'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 any matrix obtained by replacing the stars in $H$ by nonzero field elements and thus the co-dimension of the code.
We point out connections of the visible rank to other notions in the literature such as unique restricted graph matchings, matroids, spanoids, and min-rank. In particular, 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 (2020). Using this connection and a construction of appropriate stencils, we answer a question posed by Dvir, Gopi, Gu, and Wigderson (2020) and demonstrate that the 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$. This also pins down the efficacy of visible rank as a proxy for the dimension of LCCs.
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 codes with $2$-DRGP must have co-dimension $\Omega(\sqrt{n})$ (which is matched by a simple product code construction). We show that there are stencils corresponding to $2$-DRGP codes with visible rank as small as $O(\log{n})$. However, we show that the second tensor power of any $2$-DRGP stencil has visible rank $\Omega(n)$, thus recovering the $\Omega(\sqrt{n})$ lower bound on the co-dimension of $2$-DRGP codes. More broadly, we show that visible ranks of tensor powers yield sharper lower bounds on the co-dimension of the code. For $q$-LCCs, however, the $k$'th tensor power for $k \le 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. Inspired by this and as a notion of intrinsic interest, we define the notion of \emph{visible capacity} of a stencil as the limiting visible rank of high tensor powers, analogous to Shannon capacity, and pose the question of whether there can be large gaps between visible capacity and algebraic rank.Fri, 20 Oct 2023 01:17:07 +0300https://eccc.weizmann.ac.il/report/2021/119#revision2
Revision 1
| Visible Rank and Codes with Locality |
Omar Alrabiah,
Venkatesan Guruswami
https://eccc.weizmann.ac.il/report/2021/119#revision1We 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 "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 point out connections of the visible rank to other notions in the literature such as unique restricted graph matchings, matroids, spanoids, and min-rank. In particular, we prove a rank-nullity type theorem relating visible rank to the rank of an associated construct called symmetric spanoid, which was introduced by Dvir, Gopi, Gu, and Wigderson [DGGW20]. Using this connection and a construction of appropriate stencils, we answer a question posed in [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$. This also pins down the efficacy of visible rank as a proxy for the dimension of LCCs.
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 codes with $2$-DRGP must have co-dimension $\Omega(\sqrt{n})$ (which is matched by a simple product code construction). 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 $k\le 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. Inspired by this and as a notion of intrinsic interest, we define the notion of visible capacity of a stencil as the limiting visible rank of high tensor powers, analogous to Shannon capacity, and pose the question whether there can be large gaps between visible capacity and algebraic rank.Sun, 29 Aug 2021 02:45:12 +0300https://eccc.weizmann.ac.il/report/2021/119#revision1
Paper TR21-119
| Visible Rank and Codes with Locality |
Omar Alrabiah,
Venkatesan Guruswami
https://eccc.weizmann.ac.il/report/2021/119We 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 "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 point out connections of the visible rank to other notions in the literature such as unique restricted graph matchings, matroids, spanoids, and min-rank. In particular, we prove a rank-nullity type theorem relating visible rank to the rank of an associated construct called symmetric spanoid, which was introduced by Dvir, Gopi, Gu, and Wigderson [DGWW]. Using this connection and a construction of appropriate stencils, we answer a question posed in [DGGW] 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$. This also pins down the efficacy of visible rank as a proxy for the dimension of LCCs.
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 codes with $2$-DRGP must have co-dimension $\Omega(\sqrt{n})$ (which is matched by a simple product code construction). 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 $k\le 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. Inspired by this and as a notion of intrinsic interest, we define the notion of visible capacity of a stencil as the limiting visible rank of high tensor powers, analogous to Shannon capacity, and pose the question whether there can be large gaps between visible capacity and algebraic rank.Fri, 13 Aug 2021 17:04:34 +0300https://eccc.weizmann.ac.il/report/2021/119