论文标题
在熵和几乎多线性的代表性上
On entropic and almost multilinear representability of matroids
论文作者
论文摘要
本文研究了由算法信息理论和密码秘密共享动机的两种广义矩阵表示的概念。第一个（熵的表示）涉及离散的随机变量，而第二个（几乎是multilinear的表示性）涉及近似的子空间排列。在这两种情况下，我们都证明确定输入矩阵是否具有这样的表示。因此，有条件的独立性含义问题也是不可决定的，这为盖格和珍珠提出的问题提供了独立的答案，该问题最近由Cheuk Ting Li解决。这些问题也与表征网络编码和构建秘密共享方案中可实现的速率密切相关。例如，我们工作的另一个推论是，确定访问结构是否承认理想的秘密共享计划是不可决定的。我们的方法减少了从小组理论到矩阵表示问题的不可决定的问题。具体而言，我们将有限群体的统一单词问题减少到熵的可表示性和索菲群体的单词问题，以几乎单向的表示。此还原的一个关键部分涉及将组演示文稿修改为形式，在这种形式中，在限于生成集时，线性表示在适当意义上是通用的。
This article studies two notions of generalized matroid representations motivated by algorithmic information theory and cryptographic secret sharing. The first (entropic representability) involves discrete random variables, while the second (almost-multilinear representability) deals with approximate subspace arrangements. In both cases, we prove that determining whether an input matroid has such a representation is undecidable. Consequently, the conditional independence implication problem is also undecidable, providing an independent answer to a question posed by Geiger and Pearl, recently resolved by Cheuk Ting Li. These problems are also closely related to characterizing achievable rates in network coding and constructing secret sharing schemes. For example, another corollary of our work is that deciding whether an access structure admits an ideal secret sharing scheme is undecidable. Our approach reduces undecidable problems from group theory to matroid representation problems. Specifically, we reduce the uniform word problem for finite groups to entropic representability and the word problem for sofic groups to almost-multilinear representability. A key part of this reduction involves modifying group presentations into forms where linear representations are generic in an appropriate sense when restricted to the generating set.
