Computer-Aided Investigation of Information-Theoretic Limits: An Overview. (2nd part)

Abstract: The linear programming (LP) formulation of information measures provides a solid mathematical framework to identify the fundamental limits of information systems computationally. A critical issue of this approach is however its high computational complexity. To reduce the computation burden of this approach, we can utilize the symmetry structure in such systems. The strength of the symmetry-reduced approach is illustrated in several well-known difficult problems, such as regenerating codes, coded caching, and private information retrieval, which provides new and non-trivial outer bounds. In addition to rate bounds, more in-depth studies can be conducted on the joint entropy structure of these computed bounds, which often lead to reverse-engineered novel code constructions and further allow disproving linear code achievability. Finally, we discuss two new directions: the first is to allow the utilization of non-Shannon-type inequalities in the computational approach, and the second is to convert the original LP into a sequence of smaller LPs, both of which appear to be awaiting certain suitable machine-learning techniques.

Computer scienceMathematics

Audience: researchers in the discipline

Seminar on Algorithmic Aspects of Information Theory

Series comments: This online seminar is a follow up of the Dagstuhl Seminar 22301, www.dagstuhl.de/en/program/calendar/semhp/?semnr=22301.