Chop and roll: Improving the cutset bound
Sudeep Kamath, Young-Han Kim · 2014
A new outer bound on the capacity region of a general noisy network with multiple messages is established. The bound considers an ordered partition of the nodes in the network, and has an intuitive interpretation as the directed information between inputs and outputs across these subsets of the partition. The standard cutset bound is recovered as a special case when the partition consists of two subsets. The new bound extends several existing bounds to the general network that were obtained for special classes of networks. Examples include the generalized network sharing (GNS) bound for graphical networks by Kamath, Tse, and Anantharam, the GNS bound for Gaussian networks by Kamath, Kannan, and Viswanath, and the generalized cutset bound for deterministic networks by Shomorony and Avestimehr. It is demonstrated by a few simple examples that the improvement over the cutset bound can be significant.