“Generalized cut-set bounds and Symmetrical Projections of Entropy region”
Dr. Amir Salimi
Wednesday, October 19, 2016 2:00 - 3:00PM EEB 248
Abstract: In this talk, we show two combinatorial optimization problems, which arise from network information theory. Many multi-terminal communication networks, content delivery networks, cache networks and distributed storage systems, can be modeled as a broadcast network. An explicit characterization of the capacity region of the general network coding problem is one of the best known open problems in network information theory. A simple set of bounds that are often used in the literature to show that certain rate tuples are infeasible are based on the graph-theoretic notion of cut. The standard cut-set bounds, however, are known to be loose in general when there are multiple messages to be communicated in the network. A new set of explicit network coding bounds, which combine different simple cuts of the network via a variety of set operations (not just the union), are established via their connections to extremal inequalities for submodular functions.
Moreover, it is known that there is a direct relationship between network coding solution and characterization of entropy region. We talk about the symmetric structures in network coding problems and their relation with symmetrical projections of entropy region and introduce new aspects of entropy inequalities. First, inequalities relating average joint entropies rather than entropies over individual subsets are studied. Second, the existence of non-Shannon type inequalities under partial symmetry is studied using the concepts of Shannon and non-Shannon groups.