The Undecidability of Network Coding, Conditional Information Inequalities, and Conditional Independence Implication

We resolve three long-standing open problems, namely the (algorithmic) decidability of network coding, the decidability of conditional information inequalities, and the decidability of conditional independence implication among random variables, by showing that these problems are undecidable. The proof is composed of a construction inspired by Herrmann's arguments on embedded multivalued database dependencies, together with a novel construction called the Fano-non-Fano network based on the Fano matroid and the non-Fano matroid.