High-Rate Storage Codes on Triangle-Free Graphs
High-Rate Storage Codes on Triangle-Free Graphs
复制标题
无三角形图上的高速存储代码
DOI：
10.1109/tit.2022.3191309
复制
发表时间：
2022
影响因子：
2.5
通讯作者：
Zemor, Gilles
中科院分区：
文献类型：
--
作者：
Barg, Alexander;Zemor, Gilles
考虑给连通图的顶点分配位，每个顶点的值是其邻居值的函数。这样的赋值的集合被称为子程序的存储代码。存储码问题可以等价地表述为最大化图上的猜谜游戏的成功概率，或者构造小速率的索引码。如果图中包含很多团，那么构造码率接近1的码是很容易的，因此在无三角形图上构造高码率码是一个自然的问题，其中构造码率码是一个非平凡的任务，但已知的结果很少。本文利用二元线性码的陪集图构造了无限族的高码率线性存储码。我们还得到了必要的条件，这样的代码有高的速率，甚至率可能接近1。我们还解决了码字中的多个擦除的校正，基于图的扩展属性导出恢复保证。最后，我们指出了线性存储代码和量子CSS代码之间的联系，链接到自举渗透和传染扩散的图形，并制定了一些开放的问题。
Consider an assignment of bits to the vertices of a connected graphwith 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 storage code of lengthon. The storage code problem can be equivalently formulated as maximizing the probability of success in a guessing game on graphs, or constructing index codes of small rate. Ifcontains 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 rateis 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.
登录
查看更多内容
影响因子：
2.5
作者：
M. Gadouleau;Søren Riis
通讯作者：
M. Gadouleau;Søren Riis
带辅助信息的广播：限制和近似广播速率
影响因子：
2.5
作者：
A. Błasiak;Robert D. Kleinberg;E. Lubetzky
通讯作者：
E. Lubetzky
正则图中的独立集
DOI：
--
发表时间：
1964
期刊：
影响因子：
--
作者：
M. Rosenfeld
通讯作者：
M. Rosenfeld
汉明环上的 Bootstrap 渗透
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
Janko Gravner;C. Hoffman;James Pfeiffer;David J Sivakoff
通讯作者：
David J Sivakoff
可修复网络的存储容量
影响因子：
2.5
作者：
A. Mazumdar
通讯作者：
A. Mazumdar