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

DOI10.1109/TIT.2023.3247570arXiv2205.11461OpenAlexW4321488318MaRDI QIDQ6198917

Cheuk Ting Li

Publication date: 21 March 2024

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2205.11461

zbMATH Keywords

network codingindex codingconditional independence implicationconditional information inequalitiesTuring undecidability

Mathematics Subject Classification ID

Information and communication theory, circuits (94-XX)

Related Items (1)

Axiomatization of implication for probabilistic independence and unary variants of marginal identity and marginal distribution equivalence

This page was built for publication: Undecidability of Network Coding, Conditional Information Inequalities, and Conditional Independence Implication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6198917)