Finding the capacity of next-generation networks by linear programming

Proving or disproving an information inequality is a crucial step in establishing the converse results in the coding theorems of communication networks. However, next-generation networks are very large-scale, typically involving multiple users and many transceivers and relays. This means that an information inequality involving many random variables can be difficult to be proved or disproved manually. In [1], Yeung developed a framework that uses linear programming for verifying linear information inequalities, and it was recently shown in [2] that this framework can be used to explicitly construct an analytic proof of an information inequality or an analytic counterexample to disprove it if the inequality is not true in general. In this paper, we consider the construction of the smallest counterexample, and also give sufficient conditions for that the inequality can be manipulated to become true. We also describe the software development of automating this analytical framework enabled by cloud computing to analytically verify information inequalities in large-scale problem setting.