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 条
[1]  
Khamis MA, 2020, Arxiv, DOI arXiv:2004.08783
[2]   Network information flow [J].
Ahlswede, R ;
Cai, N ;
Li, SYR ;
Yeung, RW .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2000, 46 (04) :1204-1216
[3]   UNDECIDABILITY OF THE IDENTITY PROBLEM FOR FINITE-SEMIGROUPS [J].
ALBERT, D ;
BALDINGER, R ;
RHODES, J .
JOURNAL OF SYMBOLIC LOGIC, 1992, 57 (01) :179-192
[4]  
[Anonymous], 1947, The Journal of Symbolic Logic, DOI DOI 10.1126/science.1200520
[5]  
[Anonymous], 1963, Lectures on general algebra
[6]  
[Anonymous], 1984, Statistica
[7]  
[Anonymous], 2004, P 42 ALL ANN C COMM
[8]   Index Coding With Side Information [J].
Bar-Yossef, Ziv ;
Birk, Yitzhak ;
Jayram, T. S. ;
Kol, Tomer .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2011, 57 (03) :1479-1494
[9]   Network Coding Theory: A Survey [J].
Bassoli, Riccardo ;
Marques, Hugo ;
Rodriguez, Jonathan ;
Shum, Kenneth W. ;
Tafazolli, Rahim .
IEEE COMMUNICATIONS SURVEYS AND TUTORIALS, 2013, 15 (04) :1950-1978
[10]   Network routing capacity [J].
Cannons, J ;
Dougherty, R ;
Freiling, C ;
Zeger, K .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (03) :777-788
123456789