On entropic and almost multilinear representability of matroids

We study 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…