Symmetry Reduction of Information Inequalities Conference Paper uri icon

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)

published proceedings

  • 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton)

author list (cited authors)

  • Zhang, K., & Tian, C.

complete list of authors

  • Zhang, Kai||Tian, Chao

publication date

  • January 1, 2016 11:11 AM