Applications of Matroid Theory to Index and Network Coding
Event details
| Date | 17.06.2009 |
| Hour | 11:15 |
| Speaker | Dr Salim El Rouayheb |
| Location | |
| Category | Conferences - Seminars |
A major result in network coding theory is determining the capacity of noise and interference free multicast networks. However, a full understanding of the flow of information in networks with general demands faces numerous obstacles and remains an elusive goal. In this talk, we shed some light on this problem by investigating underlying connections to source coding and matroid theory. We start by showing that the general network coding problem can be reduced to a special source coding problem with side information, known as the index coding problem. This reduction implies that it is sufficient to focus on a family of networks with a special topology, simplifying thus the problem description and linking it to problems in graph theory and zero-error information theory. Then, we describe a construction that ties the linear representation properties of a given matroid to the existence of optimal index codes. This new construction strengthens previous related results in the literature and establishes a deeper connection between network coding and the rich field of matroid theory. Joint work with Alex Sprintson and Costas N. Georghiades.
Practical information
- General public
- Free