Symmetry Reduction of Information Inequalities
Conference Paper
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
2016 IEEE. 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, Plya counting theorem can be applied, which however requires identifying the cycle index of the induced permutation.
name of conference
2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton)
