A major result in network coding theory is determining the capacity of error-free information networks with multicast demands. Unfortunately, the leap to analyzing more general networks faces numerous obstacles, and, despite on-going intensive research efforts, the information flow in networks with arbitrary demands is still far from being well-understood. In this talk, we shed some light on this problem by relating it to two other different problems in source coding and matroid theory.
We start by showing that the general network coding problem can be reduced to a special case of source coding problem with side information, known as the index coding problem. Our reduction implies that it is sufficient to focus, without any loss of generality, on a family of networks with restricted topology, hence, simplifying the problem description and linking it to problems in graph coloring and zero-error information theory. Then, we describe a construction that ties the linear representation properties of a given matroid to the existence of certain index codes. This new construction strengthens previous results in the literature establishing a deeper connection between network coding and the rich field of matroid theory.