  This article is concerned with two notions of generalized matroid
representations motivated by information theory and computer science. The first
involves representations by discrete random variables and the second
approximate representations by subspace arrangements. In both cases we show
that there is no algorithm that checks whether such a representation exists. As
a consequence, the conditional independence implication problem is undecidable,
which gives an independent answer to a question in information theory by Geiger
and Pearl that was recently also answered by Cheuk Ting Li. These problems are
closely related to problems of characterizing the achievable rates in certain
network coding problems and of constructing secret sharing schemes. Our methods
to approach these problems are mostly algebraic. Specifically, they involve
reductions from the uniform word problem for finite groups and the word problem
for sofic groups.
