Constrained Linear Representability of Polymatroids and Algorithms for Computing Achievability Proofs in Network Coding
Constrained Linear Representability of Polymatroids and Algorithms for Computing Achievability Proofs in Network Coding
复制标题
DOI：
--
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Jayant Apte;J. Walsh
中科院分区：
文献类型：
--
作者：
Jayant Apte;J. Walsh
多拟阵的约束线性可表示性问题（CLRP）决定了是否存在一个多拟阵在一个指定域上是线性的，同时满足秩函数上的一组约束。利用计算机测试多源网络编码实例中的向量线性网络码是否能达到一定的速率向量，以及对于给定的秘密共享实例，是否存在能达到指定信息比的多线性秘密共享方案，这些都是CLRP的特殊情况。解决CLRP建立从群论技术组合生成的方法开发和描述。这些技术形成的核心信息理论的可验证性证明，实现伴随着文章，并提供了几个计算实验与有趣的网络编码和秘密共享的实例证明该方法的实用性。
The constrained linear representability problem (CLRP) for polymatroids determines whether there exists a polymatroid that is linear over a specified field while satisfying a collection of constraints on the rank function. Using a computer to test whether a certain rate vector is achievable with vector linear network codes for a multi-source network coding instance and whether there exists a multi-linear secret sharing scheme achieving a specified information ratio for a given secret sharing instance are shown to be special cases of CLRP. Methods for solving CLRP built from group theoretic techniques for combinatorial generation are developed and described. These techniques form the core of an information theoretic achievability prover, an implementation accompanies the article, and several computational experiments with interesting instances of network coding and secret sharing demonstrating the utility of the method are provided.