Linear Network Coding Multicast: A Theoretical Minimum and An Open Problem

NOV 11, 2016 | 2:30 PM TO 3:30 PM



The Graduate Center
365 Fifth Avenue




November 11, 2016: 2:30 PM-3:30 PM




Algebra and Cryptography Seminar


Speaker: Emina Sojanin (Rutgers University)
Abstract: Network coding is an elegant mathematical technique introduced at the turn of the millennium to improve network throughput and performance. Consider a directed acyclic graph (network) where h source-nodes produce elements of some finite field (source symbols). Edges carry linear combinations of their parent node inputs. In turn, this implies that edges throughout the network carry linear combinations of the source symbols. The network coding multicast problem asks: How should nodes in such a network with N receivers combine their inputs to ensure that each h edges observed by a receiver carry independent combinations of the source symbols? Moreover, what is the minimum field size necessary to realize combinations with this property? The field size problem is completely solved in the case of two sources and arbitrarily many receivers, but in no other cases. This talk will show how graph theory and algebraic geometry have been instrumental in proving the two-source case and gaining some further insights.