2021/07/22 by Joshua Brakensiek, Sivakanth Gopi, Brakensiek, Joshua +3 · 2 citations
Computer Science · #Advanced Data Storage Technologies #Caching and Content Delivery #Computational Complexity (cs.CC) #Cooperative Communication and Network Coding #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2107.10822
openalex publication_date 2021/07/22 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
An (m,n,a,b)-tensor code consists of m\× n matrices whose columns\nsatisfy `a' parity checks and rows satisfy `b' parity checks (i.e., a\ntensor code is the tensor product of a column code and row code). Tensor codes\nare useful in distributed storage because a single erasure can be corrected\nquickly either by reading its row or column. Maximally Recoverable (MR) Tensor\nCodes, introduced by Gopalan et al., are tensor codes which can correct every\nerasure pattern that is information theoretically possible to correct. The main\nquestions about MR Tensor Codes are characterizing which erasure patterns are\ncorrectable and obtaining explicit constructions over small fields.\n In this paper, we study the important special case when a=1, i.e., the\ncolumns satisfy a single parity check equation. We introduce the notion of\nhigher order MDS codes (MDS(\ℓ) codes) which is an interesting\ngeneralization of the well-known MDS codes, where \ℓ captures the order of\ngenericity of points in a low-dimensional space. We then prove that a tensor\ncode with a=1 is MR iff the row code is an MDS(m) code. We then show that\nMDS(m) codes satisfy some weak duality. Using this characterization and\nduality, we prove that (m,n,a=1,b)-MR tensor codes require fields of size\nq=\Ωm,b(n^\min b,m -1). Our lower bound also extends to the\nsetting of a>1. We also give a deterministic polynomial time algorithm to\ncheck if a given erasure pattern is correctable by the MR tensor code (when\na=1).\n