Beyond the Cut Set Bound: Uncertainty Computations in Network Coding With Correlated Sources
Cut-set bounds on achievable rates for network communication protocols are not in general tight. In this paper the authors introduce a new technique for proving converses for the problem of transmission of correlated sources in networks that result in bounds that are tighter than the corresponding cut-set bounds. The technique works as follows: on one hand they show that if the communication problem is solvable, the uncertainty of certain random variables in the network with respect to imaginary parties that have partial knowledge of the sources must satisfy some constraints that depend on the network architecture. On the other hand, the same uncertainties have to satisfy constraints that only depend on the joint distribution of the sources.