High-Rate Storage Codes on Triangle-Free Graphs
From MaRDI portal
Publication:6195802
DOI10.1109/TIT.2022.3191309arXiv2110.02378OpenAlexW3204553207MaRDI QIDQ6195802FDOQ6195802
Authors: Alexander Barg, Gilles Zémor 
Publication date: 14 March 2024
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: Consider an assignment of bits to the vertices of a connected graph with the property that the value of each vertex is a function of the values of its neighbors. A collection of such assignments is called a {em storage code} of length on . The storage code problem can be equivalently formulated as maximizing the probability of success in a {em guessing game} on graphs, or constructing {em index codes} of small rate. If contains many cliques, it is easy to construct codes of rate close to 1, so a natural problem is to construct high-rate codes on triangle-free graphs, where constructing codes of rate is a nontrivial task, with few known results. In this work we construct infinite families of linear storage codes with high rate relying on coset graphs of binary linear codes. We also derive necessary conditions for such codes to have high rate, and even rate potentially close to one. We also address correction of multiple erasures in the codeword, deriving recovery guarantees based on expansion properties of the graph. Finally, we point out connections between linear storage codes and quantum CSS codes, a link to bootstrap percolation and contagion spread in graphs, and formulate a number of open problems.
Full work available at URL: https://arxiv.org/abs/2110.02378
Cited In (2)
This page was built for publication: High-Rate Storage Codes on Triangle-Free Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6195802)
