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

被引：10
作者：
Li, Cheuk Ting [1 ]
机构：
[1] Chinese Univ Hong Kong, Dept Informat Engn, Hong Kong, Peoples R China
来源：
IEEE TRANSACTIONS ON INFORMATION THEORY | 2023年 / 69卷 / 06期
关键词：
Network coding; Random variables; Cramer-Rao bounds; Channel coding; Indexes; Databases; Time complexity; conditional information inequalities; conditional independence implication; index coding; Turing undecidability; ALGORITHMIC PROPERTIES; AXIOMS;
D O I：
10.1109/TIT.2023.3247570
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
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.
引用
收藏
页码：3493 / 3510
页数：18
相关论文
共 85 条
[31]   Facets of Distribution Identities in Probabilistic Team Semantics [J].
Hannula, Miika ;
Hirvonen, Asa ;
Kontinen, Juha ;
Kulikov, Vadim ;
Virtema, Jonni .
LOGICS IN ARTIFICIAL INTELLIGENCE, JELIA 2019, 2019, 11468 :304-320
[32]  
Harvey N. J. A., 2005, THESIS MIT CAMBRIDGE
[33]   ON THE UNDECIDABILITY OF IMPLICATIONS BETWEEN EMBEDDED MULTIVALUED DATABASE DEPENDENCIES [J].
HERRMANN, C .
INFORMATION AND COMPUTATION, 1995, 122 (02) :221-235
[34]  
HERRMANN C, 1987, ACTA SCI MATH, V51, P93
[35]   On the undecidability of implications between embedded multivalued database dependencies (vol 122, pg 221, 1995) [J].
Herrmann, Christian .
INFORMATION AND COMPUTATION, 2006, 204 (12) :1847-1851
[36]   Proving and Disproving Information Inequalities: Theory and Scalable Algorithms [J].
Ho, Siu-Wai ;
Ling, Lin ;
Tan, Chee Wei ;
Yeung, Raymond W. .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2020, 66 (09) :5522-5536
[37]   A random linear network coding approach to multicast [J].
Ho, Tracey ;
Medard, Muriel ;
Koetter, Ralf ;
Karger, David R. ;
Effros, Michelle ;
Shi, Jun ;
Leong, Ben .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (10) :4413-4430
[38]  
Huang Wentao., 2013, NETWORK CODING NET C, P1
[39]   Polynomial time algorithms for multicast network code construction [J].
Jaggi, S ;
Sanders, P ;
Chou, PA ;
Effros, M ;
Egner, S ;
Jain, K ;
Tolhuizen, LMGA .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (06) :1973-1982
[40]   Conditional Information Inequalities for Entropic and Almost Entropic Points [J].
Kaced, Tarik ;
Romashchenko, Andrei .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2013, 59 (11) :7149-7167
123456789