Undecidability of Network Coding, Conditional Information Inequalities, and Conditional Independence Implication
arXiv:2205.11461 · doi:10.1109/TIT.2023.3247570
Abstract
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 utilizes a construction inspired by Herrmann's arguments on embedded multivalued database dependencies, a network studied by Dougherty, Freiling and Zeger, together with a novel construction to represent group automorphisms on top of the network.
arXiv comment20 pages, 8 figures
References in corpus (5)
- Non-Shannon Information Inequalities in Four Random Variables
- Quantifier Elimination for Statistical Problems
- Conditional Information Inequalities for Entropic and Almost Entropic Points
- Representability of Matroids by c-Arrangements is Undecidable
- On entropic and almost multilinear representability of matroids