Computing network coding capacity is a hard problem since it requires a complete characterization of all feasible entropy vectors. By relaxing the set of entropy vectors to polymatroids, we obtain the Linear Programming (LP) bound which is theoretically computable but it is practically infeasible due to the enormous computational complexity. This talk will focus on a further relaxation of the LP bound by identifying the bottlenecks of a network. We term these bottlenecks as irreducible sets and give algorithms to compute them. We characterize bounds for networks with independent sources as well as correlated sources using graph theoretic and geometrical approaches. Moreover, we demonstrate the utility of the notion of irreducible sets to drastically reduce the problem size and thus computational requirement of the LP bound. These ideas are applicable for compact representation and faster computation of many problems involving system of linear inequalities and equalities in the entropy space, for example, proving constrained inequalities using Information Theoretic Inequality Prover.
Satyajit Thakor is a PhD student at the Institute for Telecommunications Research, University of South Australia. He received his B.Eng. from Dr. B. A. M. University, India and M.Eng. from University of South Australia in 2004 and 2006 respectively. He was a recipient of the Endeavour Research Fellowship 2009. His research interest is in the field of information theory and network coding.
