Symmetry reduction of information inequalities
Kai Zhang, Chao Tian · 2016
Information inequalities can be used to bound the fundamental limits of communication systems and data storage systems. Information inequalities, particularly Shannon-type inequalities, and the problem-specific constraints are usually either linear equalities or inequalities of joint entropies, and thus outer bounding the fundamental limit can be viewed and solved as a linear program (LP). However, for many practical engineering problems, the resultant LP is very large. It was shown previously that symmetry in these problems can be used to reduce the scale of the LP, however the precise amount of reduction was not well understood. In this work, we provide a generic method to pinpoint this reduction. In particular, three problems are studied: extremal pairwise cyclic entropy inequalities, the regenerating code problem, and the caching problem. By viewing the symmetry as an induced permutation group on certain set, Pólya counting theorem can be applied, which however requires identifying the cycle index of the induced permutation.